문제
N x M 도화지에서 1로 연결된 그림의 개수와 가장 넓은 그림의 넓이를 구하라.
입력
첫째 줄에 N, M, 이후 N줄에 도화지 상태가 주어진다 (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 | 4 9 |
풀이
BFS로 연결 컴포넌트를 탐색하여 그림 개수와 최대 넓이를 구한다.
- 모든 칸을 순회하며 미방문 1인 칸에서 BFS를 시작한다
- BFS에서 4방향 인접한 1인 칸의 개수(넓이)를 센다
- 그림 개수를 증가시키고, 최대 넓이를 갱신한다
핵심 아이디어: 플러드 필 알고리즘으로 각 연결 컴포넌트의 크기를 구한다.
코드
package day549;
import java.util.*;
import java.io.*;
public class Day543BOJ1926그림 {
static int N, M;
static int[] dr = { 1, 0, -1, 0 }, dc = { 0, 1, 0, -1 };
static int[][] arr;
static boolean[][] visit;
static Queue<Pair> qu;
public static void main(String args[]) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N][M];
visit = new boolean[N][M];
qu = new LinkedList<>();
for (int i = 0; i < N; i++) {
st = new StringTokenizer(bf.readLine());
for (int j = 0; j < M; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
int count = 0;
int area = 0;
int max = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (arr[i][j] == 0 || visit[i][j]) {
continue;
}
count++;
qu.offer(new Pair(i, j));
visit[i][j] = true;
area = 0;
while (!qu.isEmpty()) {
Pair p = qu.poll();
area++;
for (int k = 0; k < 4; k++) {
int nr = p.x + dr[k];
int nc = p.y + dc[k];
if (nr < 0 || nr >= N || nc < 0 || nc >= M) {
continue;
}
if (arr[nr][nc] == 1 && !visit[nr][nc]) {
qu.offer(new Pair(nr, nc));
visit[nr][nc] = true;
}
}
}
if (area > max) {
max = area;
}
}
}
System.out.println(count);
System.out.println(max);
}
public static class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
}복잡도
- 시간: O(NM)
- 공간: O(NM)