[JAVA] 백준 16949 - 벽 부수고 이동하기 4

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

 1과 0으로 이루어진 2차원 배열이 주어지며, 1은 벽이고 0은 빈 공간일 때, 각 벽을 부쉈을 때 도달가능한 빈 공간의 개수(부순 벽 포함) -> 빈 공간 영역의 각 칸수의 합 + 1이다.

 

각 영역에 번호를 붙인 뒤 탐색한 칸수를 <번호, 개수>쌍으로 HashMap에 저장하고 벽을 탐색하며 인접한 영역의 칸수를 더한 뒤 1을 더하고, 10으로 나눴다.

 

마지막 과정을 stream + distinct + toArray로 했다가 시간초과, Set으로 바꿔도 시간초과가 나서 결국 초기 탐색 방식을  DFS를 BFS로 수정하고 통과했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, 1, -1, 0};
    static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] info = getArray(br.readLine());
        map = new int[info[0]][info[1]];
        int[][] answer = new int[info[0]][info[1]];
        for (int i = 0; i < info[0]; i++) {
            char[] temp = br.readLine().toCharArray();
            for (int j = 0; j < temp.length; j++) {
                map[i][j] = Character.getNumericValue(temp[j]);
                if (map[i][j] == 1) map[i][j] = -1;
            }
        }
        boolean[][] visited = new boolean[info[0]][info[1]];
        int idx = 1;
        for (int i = 0; i < info[0]; i++) {
            for (int j = 0; j < info[1]; j++) {
                if (visited[i][j]) continue;
                if (map[i][j] == 0) {
                    bfs(i, j, visited, idx++);
                }
            }
        }
        HashMap<Integer, Integer> countMap = new HashMap<>();
        for (int i = 0; i < info[0]; i++) {
            for (int j = 0; j < info[1]; j++) {
                if (map[i][j] != -1) {
                    countMap.put(map[i][j], countMap.getOrDefault(map[i][j], 0) + 1);
                }
            }
        }
        countMap.put(0, 0);
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < info[0]; i++) {
            for (int j = 0; j < info[1]; j++) {
                if (map[i][j] == -1) {
                    set.clear();
                    for (int k = 0; k < 4; k++) {
                        int tx = i + dx[k];
                        int ty = j + dy[k];
                        if (check2(tx, ty)) {
                            set.add(map[tx][ty]);
                        }
                    }
                    int sum = 0;
                    for (Integer t : set) {
                        sum += countMap.get(t);
                    }
                    answer[i][j] = sum + 1;
                    answer[i][j] %= 10;
                }
            }
        }
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                System.out.print(answer[i][j]);
            }
            System.out.println();
        }
    }

    static void dfs(int i, int j, boolean[][] visited, int idx) {
        if (visited[i][j]) return;
        visited[i][j] = true;
        map[i][j] = idx;
        for (int k = 0; k < 4; k++) {
            int tx = i + dx[k];
            int ty = j + dy[k];
            if (check(tx, ty, visited)) {
                dfs(tx, ty, visited, idx);
            }
        }
    }

    static void bfs(int i, int j, boolean[][] visited, int idx) {
        Location16946 start = new Location16946(i, j);
        Queue<Location16946> q = new LinkedList<>();
        q.offer(start);
        while (!q.isEmpty()) {
            Location16946 s = q.poll();
            int ti = s.i;
            int tj = s.j;
            if (visited[ti][tj]) continue;
            visited[ti][tj] = true;
            map[ti][tj] = idx;
            for (int k = 0; k < 4; k++) {
                int tx = ti + dx[k];
                int ty = tj + dy[k];
                if (check(tx, ty, visited)) {
                    q.offer(new Location16946(tx, ty));
                }
            }
        }
    }

    static boolean check(int i, int j, boolean[][] visited) {
        if (i < 0 || i >= visited.length) return false;
        if (j < 0 || j >= visited[0].length) return false;
        if (visited[i][j]) return false;
        if (map[i][j] == -1) return false;
        return true;
    }

    static boolean check2(int i, int j) {
        if (i < 0 || i >= map.length) return false;
        if (j < 0 || j >= map[0].length) return false;
        if (map[i][j] == -1) return false;
        return true;
    }

    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class Location16946 {
    int i;
    int j;

    Location16946(int i, int j) {
        this.i = i;
        this.j = j;
    }
}