백준 1926번 <그림>

백준 알고리즘 1926번

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

1926번: 그림

---

1926번

도화지에 그려져있는 그림의 개수와 그림 중 가장 넓이가 큰 그림의 넓이를 구하여라.

(도화지에서 1로 나타나는 부분이 그림을 나타내고 1로 가로, 세로로 연결된 것이 하나의 그림이다.)

 

입력으로 첫 줄에 도화지의 세로 크기 n과 가로 크기 m이 주어지고 그 다음 n개의 줄에 걸쳐 도화지에 대한 정보가 들어온다.

 

출력으로 도화지에 그려져 있는 그림의 개수와 그림 중 가장 넓이가 큰 그림의 넓이를 출력한다.

---

문제 해결

BFS로 해결할 수 있다.

 

도화지의 정보를 저장한 map 배열과 방문했는지를 의미하는 visit 배열이 있다.

map 배열은 입력으로 주어지는 값으로 채우고 visit 배열은 map 배열의 값이 0일 경우에는 true를 1일 경우에는 false를 저장한다.

 

큐를 이용하여 각 좌표에 대해 BFS를 수행한다. 좌표를 표현하기위해 Tuple이라는 클래스를 정의했다.

visit[i][j]가 false 인 경우에 큐에 넣고 그림을 찾는다. 이때 각 그림은 서로 연결되어 있기 때문에 그림을 구성하는 하나의 좌표만 큐에 들어가도 그림 하나를 구할 수 있다. 그림을 탐색하는 동안에 넓이(Area)를 저장하고 maxArea와 비교하여 update한다. 

그림 하나를 구하고 나서 그림의 개수(cnt)를 카운트한다.

 

예외의 경우가 있는데 도화지에 그림이 없을 수도 있다. 이때는 그림의 개수와 가장 넓은 넓이 둘 다 0이다 이 경우는 입력으로 도화지의 정보를 받을 때 1이 없는 경우를 체크하여 따로 처리한다.

---

코드

package bj1926;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] inArr = br.readLine().split(" ");
		int n = Integer.parseInt(inArr[0]);
		int m = Integer.parseInt(inArr[1]);

		int[][] map = new int[n][m];
		boolean[][] visit = new boolean[n][m];
		int maxArea = 0;
		int cnt = 0;
		boolean chk = false;
		for (int i = 0; i < n; i++) {
			inArr = br.readLine().split(" ");
			for (int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(inArr[j]);
				if (map[i][j] == 1) {
					chk = true;
					visit[i][j] = false;
				} else {
					visit[i][j] = true;
				}
			}
		}
		if (!chk) {
			System.out.println(0);
			System.out.println(0);
		} else {
			int[] dx = { 1, -1, 0, 0 };
			int[] dy = { 0, -0, 1, -1 };

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (visit[i][j]) {
						continue;
					}
					cnt++;
					Queue<Tuple> queue = new LinkedList<>();
					int area = 1;
					visit[i][j] = true;
					queue.add(new Tuple(i, j));
					while (!queue.isEmpty()) {
						Tuple pop = queue.poll();
						for (int k = 0; k < 4; k++) {
							int newX = pop.x + dx[k];
							int newY = pop.y + dy[k];
							if (newX >= n || newY >= m || newX < 0 || newY < 0) {
								continue;
							}

							if (!visit[newX][newY]) {
								visit[newX][newY] = true;
								queue.add(new Tuple(newX, newY));
								area++;
							}

						}

					}
					maxArea = Math.max(maxArea, area);

				}
			}
			System.out.println(cnt);
			System.out.println(maxArea);
		}

	}

}

class Tuple {
	int x, y;

	public Tuple(int a, int b) {
		this.x = a;
		this.y = b;
	}
}

---

결과

---