ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 백준 1743번 : 음식물 피하기 (C 언어)
    c c++ 언어 공부 2023. 10. 28. 16:26

    https://www.acmicpc.net/problem/1743

     

    1743번: 음식물 피하기

    첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다.  그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다

    www.acmicpc.net

    Code:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    #include <stdio.h>
    #include <limits.h>
     
    int n, m, k;
    int arr[101][101= { 0, };
    int check[101][101= { 0, };
    int dx[] = { -1,1,0,0 };
    int dy[] = { 0,0,-1,1 };
    int max = INT_MIN;
    int count = 0;
     
    void dfs(int y, int x)
    {
        check[y][x] = 1;
        count++;
        for (int a = 0; a < 4; a++)
        {
            int yn = y + dy[a];
            int xn = x + dx[a];
            if (yn >= 1 && yn <= n && xn >= 1 && xn <= m && check[yn][xn] == 0 && arr[yn][xn]==1)
            {
                dfs(yn, xn);
            }
        }
    }
     
    int main() {
        scanf("%d %d %d"&n, &m, &k);
        int r, c;
        for (int i = 0; i < k; i++)
        {
            scanf("%d %d"&r, &c);
            arr[r][c] = 1;
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (arr[i][j] == 1&&check[i][j]==0)
                {
                    count = 0;
                    dfs(i, j);
                    if (max < count)
                    {
                        max = count;
                    }
                }
            }
        }
        printf("%d", max);
    }
    cs

    문제 설명:

    코레스코 콘도미니엄 8층은 학생들이 식사를 하는 공간인데, 학생들 중 일부가 음식물을 통로에 떨어뜨리는 문제가 발생합니다. 이 음식물들은 주위에 뭉치게 되어 큰 음식물 쓰레기가 됩니다. 이 문제에서는 통로에 떨어진 음식물 중 가장 큰 음식물의 크기를 찾는 것이 목표입니다.

    입력:

    • 첫 번째 줄에는 통로의 세로 길이 N, 가로 길이 M, 그리고 음식물 쓰레기의 개수 K가 주어집니다.
    • 다음 K개의 줄에는 음식물이 떨어진 좌표 (r, c)가 주어집니다.

    좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터를 기준으로 합니다. 입력으로 주어지는 좌표는 중복되지 않습니다.

    코드 설명:

     
    1. 먼저, 입력으로 주어진 통로의 크기와 음식물의 좌표를 입력 받습니다.
    2. 이차원 배열 "arr"을 이용하여 음식물이 떨어진 위치를 표시하고, "check" 배열을 이용하여 해당 위치를 이미 방문했는지 여부를 확인합니다.
    3. DFS 함수는 주어진 좌표로부터 상하좌우로 탐색하여 연결된 음식물의 크기를 계산합니다. 방문한 위치는 "check" 배열을 통해 표시하고 "count" 변수로 음식물의 크기를 저장합니다.
    4. 이중 반복문을 사용하여 모든 좌표를 확인하면서 음식물이 있고 아직 방문하지 않은 경우, 해당 영역을 DFS로 탐색하여 가장 큰 음식물 영역의 크기를 찾습니다.
    5. 가장 큰 음식물 크기를 "max" 변수에 저장하고 출력합니다.

Designed by Tistory.