[BOJ] 16946. 벽 부수고 이동하기 4 (🥇, 그래프 탐색)

🔗

풀이

배열의 크기는 1000 x 1000으로 각 벽에 대해서 매번 인접한 이동할 수 있는 칸을 찾게 되면 시간 초과가 발생할 수 있다. 각 벽에 대해서 인접할 수 있는 칸들은 결국 벽이 아닌 칸(0)들이기 때문에 이어져있는 벽이 아닌 칸들에 대해서 서로 인접해있는 칸들의 개수를 미리 구해두면 된다.

노란 칸은 서로 인접한 칸의 개수가 2칸이고, 빨간 칸은 인접한 칸의 개수가 3개이다. 이때 인접한 칸에는 자기자신도 포함된다. 그림과 같이 벽이 아닌 칸들에 대해서 서로 인접한 칸의 개수를 구했으면 이제 각 벽에 대해서 인접한 상하좌우 4칸에 대해서 벽이 아닌 칸이 나오면 해당 칸과 연결된 인접한 칸의 개수를 더해주면 된다. 해당 칸과 인접한 칸에 대해서는 Map 자료구조를 활용해 인접해있는 칸 마다 번호를 붙이고 각 번호 마다 인접한 칸의 개수를 저장하는 식으로 미리 저장해두었다.

그런데 이때 벽의 상하좌우 중에 동일한 구역과 맞닿을 때가 있다. 이런 경우를 제외하기 위해서 각 벽에 대해서 상하좌우와 인접한 벽이 아닌 칸을 구하고 해당 칸에 매겨져있는 구역의 번호를 Set 자료구조를 활용해 저장하여 중복을 제거한다.

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

public class Main {
    static int[][] direction = new int[][] {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    static int bfs(int[][] map, int x, int y, int number) {
        int[] cur;
        int nextX; 
        int nextY;
        int count = 1;
        Queue<int[]> queue = new LinkedList<>();
        map[x][y] = number;
        queue.add(new int[] {x, y});
        while (!queue.isEmpty()) {
            cur = queue.poll();

            for (int i = 0; i < 4; i++) {
                nextX = cur[0] + direction[i][0];
                nextY = cur[1] + direction[i][1];

                if (nextX < 0 || nextX >= map.length || nextY < 0 || nextY >= map[0].length || map[nextX][nextY] != 0) {
                    continue;
                } 

                map[nextX][nextY] = number;
                count++;
                queue.add(new int[] {nextX, nextY});
            }
        }

        return count;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] map = new int[N][M];
        String[] inputLine;
        for (int i = 0; i < N; i++) {
            inputLine = br.readLine().split("");
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(inputLine[j]);
            }
        }

        Map<Integer, Integer> moveCount = new HashMap();
        int number = 2;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) {
                    moveCount.put(number, bfs(map, i, j, number));
                    number++;
                }
            }
        }

        moveCount.put(1, 0);
        int[][] answer = new int[N][M];
        StringBuilder sb = new StringBuilder();
        Set<Integer> set;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 1) {
                    set = new HashSet<>();
                    answer[i][j] = 1;
                    for (int k = 0; k < 4; k++) {
                        int ni = i + direction[k][0];
                        int nj = j + direction[k][1];

                        if (ni < 0 || ni >= N || nj < 0 || nj >= M) {
                            continue;
                        }
                        
                        set.add(map[ni][nj]);
                    }

                    for (Integer key : set) {
                        answer[i][j] += moveCount.get(key); 
                    }
                }
                sb.append((answer[i][j]) % 10);
            }
            sb.append("\n");
        }   

        sb.deleteCharAt(sb.length()-1);
        System.out.println(sb);
    }
}