[백준] 16954번 : 움직이는 미로 탈출

16954번: 움직이는 미로 탈출

---

[BFS]

사람이 먼저 BFS 탐색을 하고, 그 다음 벽이 움직이는 벽 BFS가 실행된다.이 문제에서, 벽은 8턴 이후에는 맵에 없으므로(8줄이기 때문에 8턴 후 모든 벽은 사라진다) 9턴 째 까지 왔다면 탐색할 필요 없이 탈출에 성공한 것이다.

 

그래서 visit배열을 3차원 배열로 선언해 몇 번째 턴일 때 방문한 것인지 체크하였다. 플레이어는 상하좌우, 대각선, 제자리 이렇게 9곳을 탐색할 수 있다.

 

그리고 가장중요한 것은 다음과 같은 상황일 때의 처리 방법이라 생각된다.

.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
#	#	.	.	.	.	.	.
.	#	.	#	.	.	.	.
.	.	.	.	.	.	.	.

이 상태에서 1턴이 지난 후의 모습은 다음과 같아야 한다.

.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
#	#	.	.	.	.	.	.
.	#	.	#	.	.	.	.

하지만 잘못 처리를 한다면 다음과 같아질 수 있다.

.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
#	.	.	.	.	.	.	.
.	#	.	#	.	.	.	.

이러한 점을 유의하며 풀어보자

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    static class Point{
        int y, x, turn;
        public Point(int yy, int xx, int t){
            y=yy; x=xx; turn = t;
        }
    }
    static boolean escape;
    static int[] Y = {-1, 1, 0, 0, -1, -1, 1, 1, 0}, X = {0, 0, -1, 1, -1, 1, 1, -1, 0};
    static char[][] map = new char[9][9];
    static boolean[][][] visit = new boolean[9][9][9];
    static Queue<Point> wallQ = new LinkedList<>(), personQ = new LinkedList<>();

    static void wallBFS(){
        boolean[][] check = new boolean[9][9];
        Queue<Point> tmpQ = new LinkedList<>();

        while(!wallQ.isEmpty()){
            Point p = wallQ.poll();

            if(p.y < 8){

                if(!check[p.y][p.x]) {
                    check[p.y + 1][p.x] = true;
                    map[p.y][p.x] = '.';
                }

                map[p.y + 1][p.x] = '#';
                tmpQ.add(new Point(p.y + 1, p.x, 0));
            }
            else
                if(!check[p.y][p.x])
                    map[p.y][p.x] = '.';

        }
        wallQ = tmpQ;
    }
    static boolean personBFS(){
        Queue<Point> tmpQ = new LinkedList<>();

        while(!personQ.isEmpty()){
            Point p = personQ.poll();

            int y = p.y;
            int x = p.x;
            int turn = p.turn;

            if(map[y][x] == '#') continue;
            else if((y == 1 && x == 8) || turn >= 8) {
                escape = true;
                break;
            }

            for(int a=0; a<9; a++){
                int ny = y+Y[a];
                int nx = x+X[a];

                if(ny < 1 || nx < 1 || ny > 8 || nx > 8 || map[ny][nx] == '#' || visit[turn + 1][ny][nx]) continue;
                if(map[ny-1][nx] == '#') continue;

                visit[turn + 1][ny][nx] = true;
                tmpQ.add(new Point(ny, nx, turn + 1));
            }
        }
        personQ = tmpQ;
        return personQ.isEmpty();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for(int i=1; i<=8; i++){
            char[] str = br.readLine().toCharArray();
            for(int j=1; j<=8; j++){
                map[i][j] = str[j-1];

                if(map[i][j] == '#')
                    wallQ.add(new Point(i, j, 0));
            }
        }
        visit[0][8][1] = true;
        personQ.add(new Point(8, 1, 0));

        while(!escape){
            if(personBFS()) break;
            wallBFS();
        }
        System.out.println(escape? 1 : 0);
    }
}