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

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

각각의 벽에 대해서 다음을 구해보려고 한다.

• 벽을 부수고 이동할 수 있는 곳으로 변경한다.
• 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

출력

맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

예제 입력 1

3 3
101
010
101

예제 출력 1

303
050
303

예제 입력 2

4 5
11001
00111
01010
10101

예제 출력 2

46003
00732
06040
50403

풀이

이 문제는 DFS든 BFS든 어느 알고리즘을 써도 풀 수 있다. 하지만 시간을 많이 쓰는 비효율적인 구현이 되었다. 개선점을 찾아야할 것 같다.

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

public class Main {
    static int N;
    static int M;
    static int[][] map;
    static int[][] sector;
    static boolean[][] visited;
    static int[] lens = new int[500000];
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int len;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        map = new int[N][M];
        sector = new int[N][M];
        visited = new boolean[N][M];
        HashSet<Pair> set = new HashSet<>();

        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<M; j++) {
                map[i][j] = str.charAt(j) - '0';
                if(map[i][j]==1)
                    set.add(new Pair(i, j));
            }
        }

        int num = 0;
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(map[i][j]==0 && !visited[i][j]) {
                    len = 0;
                    visited[i][j] = true;
                    sector[i][j] = num;
                    dfs(i, j, num);
                    lens[num] = len;
                    num++;
                }
            }
        }

        for(Pair wall: set) {
            solution(wall);
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++)
                sb.append(map[i][j]%10);
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }

    static void solution(Pair wall) {
        HashSet<Integer> set = new HashSet<>();
        int cnt = 0;

        for(int i=0; i<4; i++) {
            int nx = wall.x+dx[i];
            int ny = wall.y+dy[i];

            if(nx<0 || nx>=N || ny<0 || ny>=M || map[nx][ny]!=0) continue;

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

        for(int i: set) {
            cnt += lens[i];
        }

        map[wall.x][wall.y] += cnt;
    }

    static void dfs(int x, int y, int num) {
        len++;

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

            if(nx<0 || nx>=N || ny<0 || ny>=M || visited[nx][ny] || map[nx][ny]!=0) continue;

            visited[nx][ny] = true;
            sector[nx][ny] = num;
            dfs(nx, ny, num);
        }
    }

    static class Pair {
        int x;
        int y;

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