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

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

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

1. 문제의 유형 및 이해

그래프 탐색

$N*M$ 행렬에 이동할 수 있는 곳을 0으로 벽을 1로 하여 주어진다.

인접한 칸을 이동하려면 두 칸이 인접해 있어야한다.

각각의 벽에 대해 벽을 부쉈을 때 그 위치에서 이동할 수 있는 칸의 개수를 세어보자.

주어지는 input의 크기는 $N<=1000, M<=1000)이다.

2. 문제 접근 방법

1. Naiive

문제에서 가장 Naiive하게 접근을 하는 방법은 각 벽에서 갈 수 있는 모든 곳에 대해 탐색해보는 방법입니다.

이 경우 주어진 행렬의 테두리가 모두 벽이라고 가정했을 때 

O(2*(N+M-2) * (N-1)(M-1))로 O($N^2M^2)의 시간 복잡도가 나오게 됩니다.

주어지는 input의 크기와 시간을 고려할 때 시간 초과가 나올 것 같습니다.

 

2. 나아가보기

시간초과가 나오는 주요한 이유 중 하나는 이미 확인한 곳에 대해 "중복"으로 확인하는데에 있습니다.

관점을 바꿔 벽이 아닌, 갈 수 있는 곳에 대해 grouping을 해두고, 각 벽에서는 인접한 곳에 갈 수 있는 group이 있는지를 확인해봅니다.  중복이 아닌 각 group들에 대해 group에 포함된 개수들을 더해준다면 이미 구한 값을 중복으로 구하게 되는 비효율적인 방법을 제거할 수 있습니다.

위의 예시의 경우 O((N-1)*(M-1)) + O(2*(N+M-2)로 O(NM)시간복잡도로 해결이 가능합니다.

 

구현의 경우 갈 수 있는 공간에 대해 BFS로 탐색하면서 group을 나누었습니다.

group들에 대해 <groupId, cnt>를 HashMap에 저장해두고, 각각의 벽에 대해 4방향을 탐색하면서 진행하였습니다. 이 때 벽의 경우 Queue를 활용하여 진행했는데, 비슷한 아이디어라도 어떻게 구현하느냐에 따라 시간이 조금씩 달라지는 것 같습니다.

 

package solvedac.level5.gold2;

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

/**
 * @문제번호 : Q17143
 * @문제이름 : 벽부수고 이동하기 4
 * @난이도 : Gold II
 * @date : 2022-02-19 오후 4:31
 * @author : pcrmcw0486
 * @문제이해
 * N*M 행렬에서 각각의 벽에 대해
 * 벽을 부수고 이동할 수 있는 곳으로 변경해보았을 때 그 위치에서
 * 이동할 수 있는 칸의 개수를 출력한다 %10해서
 * @알고리즘
 * 그래프탐색
 * @접근방법
 * 세어본것을 또 세어본다는 것 자체가 낭비임.
 * 빈 공간들에 대해 중복적으로 검사를 하게 되는데 이 부분이 매우 비효율적이라고 생각함.
 * 내 아이디어는 다음과 같음
 *  - 1. 빈 공간들에 대해 grouping 하고 ID부여
 *  - 2. 각 벽들은 현재 위치에서 중복되지 않는 ID들에 대해 값을 더해주고
 *      자신의 위치 +1을 해줌.
 * - O(NM) + 벽개수*4

 */
public class Main {
    static int[][] dir = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};
    public static void main(String[] args) throws IOException {
        Queue<Point> walls = new LinkedList<>();
        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];
        for(int i =0;i<N;i++){
            String line = br.readLine();
            for(int j=0;j<M;j++){
                if(line.charAt(j) == '0')
                    map[i][j] = 1;
                else{
                    map[i][j] = 0;
                    walls.add(new Point(i, j));
                }
            }
        }
        HashMap<Integer, Integer> groupInfo = new HashMap<>();
        Queue<Point> group;
        int groupId = 2;
        for(int i =0;i<N;i++){
            for(int j=0;j<M;j++){
                if(map[i][j] == 1){
                    int cnt =0;
                    group = new LinkedList<>();
                    map[i][j] = groupId;
                    group.add(new Point(i,j));
                    while (!group.isEmpty()) {
                        Point cur = group.poll();
                        cnt++;
                        for(int d =0;d<4;d++){
                            int nx = cur.x + dir[d][0];
                            int ny = cur.y + dir[d][1];
                            if(nx<0 || nx>N-1||ny<0 || ny>M-1) continue;
                            if(map[nx][ny] == 0) continue;
                            if(map[nx][ny] ==1) {
                                map[nx][ny] = groupId;
                                group.add(new Point(nx, ny));
                            }
                        }
                    }
                    groupInfo.put(groupId, cnt);
                    groupId++;
                }
            }
        }
        int[][] ans = new int[N][M];
        while(!walls.isEmpty()){
            Point cur = walls.poll();
            Set<Integer> checkGroup = new HashSet<>();
            int cnt =0;
            for(int i =0;i<4;i++){
                int nx = cur.x + dir[i][0];
                int ny = cur.y + dir[i][1];
                if(nx<0 || nx>N-1||ny<0 || ny>M-1) continue;
                if(map[nx][ny] == 0) continue;
                if(!checkGroup.contains(map[nx][ny])){
                    cnt += groupInfo.get(map[nx][ny]);
                    checkGroup.add(map[nx][ny]);
                }
            }
            ans[cur.x][cur.y] = (cnt+1)%10;
        }
        StringBuilder sb = new StringBuilder();
        for(int i =0;i<N;i++){
            for(int j=0;j<M;j++){
                sb.append(ans[i][j]);
            }
            sb.append('\n');
        }
        System.out.println(sb);
    }
    static class Point{
        int x,y;

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