백준 1926번 : 그림(C 언어)

Code:

#include <stdio.h>
 
int arr[501][501] = { 0, };
int n, m;
int check[501][501] = { 0, };
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int num = 0;
int max = 0;
 
void dfs(int y, int x)
{
    num += 1;
    check[y][x] = 1;
    for (int k = 0; k < 4; k++)
    {
        int x_n = x + dx[k];
        int y_n = y + dy[k];
        if (arr[y_n][x_n] == 1 && x_n >= 0 && x_n < m && y_n >= 0 && y_n < n && check[y_n][x_n] == 0)
        {
            dfs(y_n, x_n);
        }
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
    int i, j;
    int count = 0;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++)
        {
            scanf("%d", &arr[i][j]);
        }
    }
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++)
        {
            if (arr[i][j] == 1 && check[i][j] == 0)
            {
                num = 0;
                dfs(i, j);
                count++;
            }
            if (num > max)
            {
                max = num;
            }
            continue;
        }
    }
    printf("%d\n%d", count, max);
}

문제 설명: 이 문제는 주어진 도화지에 그려진 그림을 분석하는 문제입니다. 각 그림은 1로 연결된 영역을 의미하며, 그림의 개수와 그 중 가장 넓은 그림의 넓이를 구해야 합니다. 그림은 1로 연결된 영역을 의미하며, 가로나 세로로 연결된 영역은 하나의 그림으로 간주합니다. 대각선으로 연결된 영역은 별도의 그림으로 처리합니다.

코드 설명:

1. 먼저, 입력으로 도화지의 세로 크기(n)와 가로 크기(m)를 받습니다.
2. 2차원 배열 arr에 도화지의 정보를 저장합니다. 각 칸은 0 또는 1로 표시되며, 0은 색칠이 안 된 부분을 나타내고, 1은 색칠된 부분을 나타냅니다.
3. 그림의 개수를 세는 count 변수와 현재 그림의 넓이를 저장하는 num 변수, 그리고 최대 그림 넓이를 저장하는 max 변수를 초기화합니다.
4. 이중 반복문을 사용하여 도화지를 순회하면서 그림의 개수와 넓이를 구합니다.
5. 만약 현재 위치가 색칠된 부분(1)이고, 아직 방문하지 않았다면, DFS(깊이 우선 탐색)를 수행하여 현재 그림의 넓이를 구합니다.
6. DFS 함수에서는 현재 위치를 방문했음을 체크하고, 상하좌우로 인접한 위치를 확인하며 연결된 부분을 찾습니다. 연결된 부분을 찾으면 해당 위치로 이동하여 DFS를 재귀적으로 호출합니다.
7. 그림을 하나 처리할 때마다 count를 증가시키고, 현재 그림의 넓이(num)가 최대 넓이(max)보다 크다면 max를 업데이트합니다.
8. 모든 위치를 순회하면서 위 과정을 반복하고, 마지막에 그림의 개수와 최대 그림 넓이를 출력합니다.