[백준 5427] 불

 

빠른 시간이므로 BFS 로 접근해야한다.

시간이 지날때마다 사람의 이동, 불의 이동이 이루어지므로 큐를 따로 만들어 사용한다.

 

처음에는 사람 이동 -> 불 이동 순으로 구현했었는데 예제는 모두 통과하는데도 틀리다고 나왔다.

문제에 불이 옮겨옴과 동시에 이동할 수 있다는 구문을 보고 불 이동 -> 사람 이동 으로 순서를 바꾸었더니 통과했다.

불이 먼저 이동해서 사람 위치를 차지하면 사람이 안움직일줄 알았는데 이미 큐에 담겨있어서 움직일 수 있었다.

 

 

#	#	.	#	#
#	#	.	#	#
사람	사람	.	불	불
사람	#	#	#	불
사람	#	#	#	불

왜 틀렸는지에 대한 예제를 생각해냈다.

 

사람, 불은 빨간 위치에서 시작하고 현재 3칸씩 이동한 상황이다.

사람 -> 불 순으로 이동하면 사람이 (3, 3) 으로 이동하고 불이 덮는다. 사람 위치정보가 이미 큐에 담겨있으므로

사람은 이동할 수 있어서 정답이 아니게 된다.

불 -> 사람 순으로 이동하면 불이 (3, 3) 을 덮고 사람은 이동하지 못하게 된다. 불이 다가올 위치로 사람은 이동하지

못하므로 조건이 성립된다.

 

 

 

구현은 다음과 같다.

1. 불의 위치를 모두 큐에 담는다. (불은 1개 이상일 수 있다.)

2. 큐의 개수만큼 불이 이동한다. 불이 지나간 자리는 사람이 갈 수 없다.

3. 사람의 위치를 큐에 담는다.

4. 사람이 이동한다. visited 배열에 방문 기록을 담는다.

5. 1~4 를 반복하다가 사람의 큐가 비면 IMPOSSIBLE 을 출력하고 사람의 위치가 배열 밖을 배열의 끝에 도달하면

   이동 횟수를 출력한다.

 

탈출 조건은 짜기 나름인데 필자는 배열의 양쪽 공간을 확보하여 사람만 도달할 수 있게 하여 조건을 완성시켰다.

 

 

public class Main {
    
    static int h;
    static int w;
    static char[][] a;
    static int[][] distance;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int t = sc.nextInt();
        while(t-->0) {
            h = sc.nextInt() + 2;
            w = sc.nextInt() + 2;
            a = new char[w][h];
            distance = new int[w][h];
            Arrays.fill(a[0], '0');
            Arrays.fill(a[w-1], '0');
            
            int x = 0, y = 0;
            for(int i=1; i<w-1; i++) {
                String str = "0" + sc.next() + "0";
                a[i] = str.toCharArray();
                for(int j=1; j<h-1; j++) {
                    if(a[i][j] == '@') {
                        x = i;
                        y = j;
                    }
                }
            }
            bfs(x, y);
        }
    }
    
    public static void bfs(int x, int y) {
        boolean[][] visited = new boolean[w][h];
        Queue<Pair> me = new LinkedList<Pair>();
        Queue<Pair> fire = new LinkedList<Pair>();
        
        int mx[] = {0, 1, 0, -1};
        int my[] = {1, 0, -1, 0};
        
        for(int i=0; i<w; i++) {
            for(int j=0; j<h; j++) {
                if(a[i][j] == '*') {
                    fire.offer(new Pair(i, j));
                }
            }
        }
        
        me.offer(new Pair(x, y));
        visited[x][y] = true;
        distance[x][y] = 0;
        boolean success = false;
        int result = 0;
        while(!me.isEmpty()) {
            if(success) break;
            int size = me.size();
            int fsize = fire.size();
            
            while(fsize-->0) {
                Pair fpoint = fire.poll();
                int fpx = fpoint.getX();
                int fpy = fpoint.getY();
                for(int i=0; i<4; i++) {
                    int fnx = fpx + mx[i];
                    int fny = fpy + my[i];
                    if(1 <= fnx && fnx < w-1 && 1 <= fny && fny < h-1) {
                        if(a[fnx][fny] == '.' || a[fnx][fny] == '@') {
                            a[fnx][fny] = '*';
                            fire.offer(new Pair(fnx, fny));
                        }
                    }
                }
            }
            while(size-->0) {
                Pair point = me.poll();
                int px = point.getX();
                int py = point.getY();
                if(a[px][py] == '0') {success = true; result = distance[px][py];}
                for(int i=0; i<4; i++) {
                    int nx = px + mx[i];
                    int ny = py + my[i];
                    if(0 <= nx && nx < w && 0 <= ny && ny < h) {
                        if((a[nx][ny] == '.' || a[nx][ny] == '0') && !visited[nx][ny]) {
                            visited[nx][ny] = true;
                            me.offer(new Pair(nx, ny));
                            distance[nx][ny] = distance[px][py] + 1;
                        }
                    }
                }
            }
        }
        
        System.out.println(success == true ? result : "IMPOSSIBLE");
    }
    
    static class Pair {
        int x;
        int y;
        
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
        
        int getX() {
            return x;
        }
        
        int getY() { 
            return y;
        }
    }
}