[백준] 16946번 : 벽 부수고 이동하기 4

문제

16946번: 벽 부수고 이동하기 4

 

접근 방식

맵의 최대 크기가 1000 * 1000이기 때문에

매번 벽을 기준으로 BFS나 DFS를 이용해 탐색하면 시간초과가 발생한다.

 

그래서 0을 기준으로 각 구역의 크기를 계산한 후에

1을 기준으로 상하좌우로 맞닿은 구역의 크기를 더해주면 되는데

이때 중복이 있을 수 있기 때문에 Set을 사용해서 처리해 주면 된다.

 

예를 들어 현재 벽과 맞닿은 구역이 1, 1, 2, 3 구역이라면

1 구역은 한 번만 계산하면 되기 때문에 중복을 처리해

1, 2, 3 구역의 크기를 한 번씩만 계산해 주면 된다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(input[0]);
		int m = Integer.parseInt(input[1]);

		int[] dx = {-1, 1, 0, 0};
		int[] dy = {0, 0, -1, 1};
		int[][] map = new int[n][m];
		int[][] isVisited = new int[n][m];
		Queue<Pair> q = new ArrayDeque<>();

		for (int i = 0; i < n; i++) {
			input = br.readLine().split("");
			for (int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(input[j]) * -1;
			}
		}

		Map<Integer, Integer> counts = new HashMap<>();
		int num = 1;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == -1) continue;
				if (isVisited[i][j] != 0) continue;

				int cnt = 1;
				q.offer(new Pair(i, j));
				isVisited[i][j] = num;

				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 (isVisited[nx][ny] != 0 || map[nx][ny] == -1) continue;

						cnt++;
						isVisited[nx][ny] = num;
						q.offer(new Pair(nx, ny));
					}
				}

				counts.put(num++, cnt);
			}
		}

		Set<Integer> set = new HashSet<>();

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 0) {
					sb.append(0);
					continue;
				}

				int cnt = 1;

				for (int dir = 0; dir < 4; dir++) {
					int nx = i + dx[dir];
					int ny = j + dy[dir];

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

					set.add(isVisited[nx][ny]);
				}

				for (int c : set) cnt += counts.get(c);
				set.clear();

				sb.append(cnt % 10);
			}
			sb.append("\n");
		}

		System.out.println(sb);
	}

	static class Pair {
		int x, y;

		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}