[C언어] 백준 1926 그림

문제

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

입력

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

출력

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

예제 입력 1 

6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

예제 출력 1 

4
9

 

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

1926번: 그림

 

문제 풀기 전 로직 생각하기

---

칠해져 있는 영역의 갯수와 칠해져 있는 영역중 가장 넓은 넓이를 출력하는 문제입니다.

0은 칠해져 있지 않고 1은 칠해져 있는 부분으로 입력을 받으니

dfs로 배열의 값이 1인지 확인을 하면서 재귀 형식으로 풀면 될것 같습니다.

그리고 dfs를 실행한 후마다 넓이를 체크하면서 더 넓은 경우 결과 값을 초기화 시켜주면 될것 같습니다.

 

전체 코드

---

#include <stdio.h>

int map[501][501], n, m, result = 0, cnt = 0, visited[501][501] = {};

int is_in_map(int y, int x)
{
    if (0 <= x && x < m && 0 <= y && y < n)
        return (1);
    return (0);
}

void    dfs(int y, int x, int *area)
{
	// 맵을 벗어나지 않았으면서 칠해져 있는 부분이라면
    if (is_in_map(y, x) && !visited[y][x] && map[y][x])
    {
        *area += 1;
        visited[y][x]++;
        dfs(y + 1, x, area);
        dfs(y - 1, x, area);
        dfs(y, x + 1, area);
        dfs(y, x - 1, area);
    }
}

int main()
{
    int    area;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &map[i][j]);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            area = 0;
            // 방문하지 않았으면서 칠해져 있으면 카운트
            if (!visited[i][j] && map[i][j] && ++cnt)
            {
                dfs(i, j, &area);
                // 넓이가 더 넓은 경우
                if (result < area)
                    result = area;
            }
        }
    }
    printf("%d\n%d\n", cnt, result);
    return (0);
}

 

문제 해설

---

문제 풀기 전 로직 생각하기 부분에서 생각한 내용을 그대로 구현했습니다.

배열의 값이 1이면서 방문하지 않은 경우 카운트를 하며 dfs로 넓이를 구합니다.

그 후 구한 넓이의 값이 더 넓은 경우 결과값을 초기화 해준뒤 그래도 출력 후 종료하게 구현했습니다.