[Java] 백준 16946 - 벽 부수고 이동하기 4

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

 

풀이

 

1. 벽으로 나눠진 구역들에 번호를 매김 (동시에 각 구역의 칸 수도 저장해둠)
2. 특정 칸의 벽을 없앤다면 어떤 구역들이 연결되는지 보고 1번에서 구해둔 칸 수 정보를 활용해서 연결되는 칸 수 구하기

 

예를들어, X가 벽이라고 치면, 다음과 같이 나눠진 구역에 번호를 매기고

XX00X		XX11X
00XXX	=>	22XXX
0X0X0		2X3X4
X0X0X		X5X6X

 

배열에 각 구역의 칸 수를 저장해두기.

[2, 3, 1, 1, 1, 1]

 

 

1번 과정은 BFS (flood-fill)을 사용하고, 2번 과정은 그냥 벽이 있는 칸의 상하좌우만 확인해주면 됨.

 

코드

import java.io.*;
import java.util.*;

public class Main {
	public static class Pos {
		public int row, col;

		public Pos(int r, int c) {
			row = r;
			col = c;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		boolean[][] wall = new boolean[R][C];

		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				wall[r][c] = (br.read() == '1');
			}
			br.readLine();
		}

		int[][] map = new int[R][C];
		int areaNum = 0;
		int[] areaSize = new int[R * C + 1];
		int[] dirR = { -1, 1, 0, 0 };
		int[] dirC = { 0, 0, -1, 1 };

		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (map[r][c] == 0 && !wall[r][c]) {
					areaNum++;
					areaSize[areaNum] = 1;
					Queue<Pos> que = new LinkedList<>();
					que.add(new Pos(r, c));
					map[r][c] = areaNum;

					while (!que.isEmpty()) {
						Pos cur = que.remove();

						for (int dir = 0; dir < 4; dir++) {
							int row = cur.row + dirR[dir];
							int col = cur.col + dirC[dir];

							if (row < 0 || row >= R || col < 0 || col >= C) {
								continue;
							}

							if (wall[row][col] || map[row][col] > 0) {
								continue;
							}

							map[row][col] = areaNum;
							areaSize[areaNum]++;
							que.add(new Pos(row, col));
						}
					}
				}
			}
		}

		boolean[] checked = new boolean[areaNum + 1];
		int[][] answer = new int[R][C];

		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (wall[r][c]) {
					answer[r][c] = 1;

					for (int dir = 0; dir < 4; dir++) {
						int row = r + dirR[dir];
						int col = c + dirC[dir];

						if (row < 0 || row >= R || col < 0 || col >= C) {
							continue;
						}

						if (checked[map[row][col]]) {
							continue;
						}

						answer[r][c] += areaSize[map[row][col]];
						checked[map[row][col]] = true;
					}

					for (int dir = 0; dir < 4; dir++) {
						int row = r + dirR[dir];
						int col = c + dirC[dir];

						if (row < 0 || row >= R || col < 0 || col >= C) {
							continue;
						}

						checked[map[row][col]] = false;
					}
				}
			}
		}

		StringBuilder sb = new StringBuilder();

		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				sb.append(answer[r][c] % 10);
			}
			sb.append('\n');
		}

		System.out.println(sb);
		br.close();
	}
}