[1926] 그림

그림 🪙

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

입력

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

출력

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

예제

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

output
4
9

---

풀이

BFS로 풀 수 있는 기본 유형의 문제라고 할 수 있다. 큰 도화지(map)을 탐색하면서 그림의 개수와 가장 큰 그림의 넓이를 알아내면 된다. 이때 그림은 1로 연결된 것들을 의미한다.

그림의 개수와 최대 넓이는 다음과 같은 순서로 찾을 수 있다.

자세한 풀이

1. 그림을 찾을 때까지 도화지를 탐색한다. (map[i][j] == 1인걸 찾을때까지 이중for문으로 탐색한다)
2. 처음으로 그림의 일부를 찾았다면 그림은 모두 연결되어 있기 때문에 주변을 탐색하며 그림의 넓이를 구한다. (bfs)
3. 찾은 그림은 다시 찾지 않기 위해서 이미 방문했다는 체크를 해 놓는다(visited 배열 활용)
4. 다시 다른 그림을 찾기 위해 도화지를 탐색한다
5. 그림의 일부를 찾았다면 이미 찾았던 그림인지 확인해본다(visited[i][j] == 1이면 이미 찾았던 그림)
6. 아니라면 2~3번 과정을 반복한다.
7. 도화지를 모두 탐색했다면 지금까지 찾은 그림의 개수와 그림의 최대 넓이를 출력한다.

bfs를 이용해서 그림의 조각에서부터 전체 그림을 탐색하고, 그림의 넓이를 구하면 되는 문제이다. 이때 이미 찾았던(방문했던) 그림이라면 재방문하는게 비효율적이므로 방문 확인용 2차원 배열(visited)을 통해 방문여부를 저장한다.

그림의 개수

새로운 그림의 조각(map[i][j] == 1 && !visited[i][j])을 찾아내면 한번의 bfs로 전체 그림을 찾아내기(방문하기)때문에 도화지를 탐색할 때 이전에 방문하지 않았던 그림의 조각(map[i][j] == 1)을 찾아낸(방문한) 횟수가 그림의 개수이다. 즉, 새롭게 bfs를 실행하는 횟수가 그림의 개수이다.

그림의 넓이

새로운 그림의 조각(map[i][j] == 1 && !visited[i][j])을 찾아내면 한번의 bfs로 전체 그림을 찾아내기(방문하기)때문에 bfs 실행 시 방문한 그림 조각(노드)의 개수가 그림의 넓이이다. 즉, bfs 실행 시 queue에서 pop되는 횟수가 그림의 넓이이다.

 

코드

// 멤버변수 선언
private static boolean[][] map = new boolean[500][500];
private static boolean[][] visited = new boolean[500][500];

// 생략

Queue<Pair> q = new LinkedList<>();
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        // 그림이고 && 방문하지 않았다면
        if (map[i][j] && !visited[i][j]) {
            cnt++; // 그림 개수 추가
            visited[i][j] = true; // 방문
            q.add(new Pair(i, j));
            int area = 0; // 그림 넓이 초기화(새로운 그림 시작)

            while (!q.isEmpty()) {
                Pair cur = q.poll();
                for (int dir = 0; dir < 4; dir++) {
                    int nx = cur.x + dx[dir];
                    int ny = cur.y + dy[dir];

                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                    if (!map[nx][ny] || visited[nx][ny]) continue;

                    visited[nx][ny] = true;
                    q.add(new Pair(nx, ny));
                }
                area++;
            }
            maxArea = Math.max(maxArea, area);
        }
    }
}
System.out.println(cnt + "\n" + maxArea);