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

문제

욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다.

이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다.

1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.

욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보자.

입력

8개 줄에 걸쳐서 체스판의 상태가 주어진다. '.'은 빈 칸, '#'는 벽이다. 가장 왼쪽 아랫칸은 항상 벽이 아니다.

출력

욱제의 캐릭터가 가장 오른쪽 윗 칸에 도착할 수 있으면 1, 없으면 0을 출력한다.

예제 입력 1

........
........
........
........
........
........
........
........

예제 출력 1

1

예제 입력 2

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

예제 출력 2

0

예제 입력 3

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

예제 출력 3

0

예제 입력 4

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

예제 출력 4

1

예제 입력 5

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

예제 출력 5

0

풀이

이 문제는 3차원 배열과 BFS 알고리즘을 사용해서 풀 수 있었다. 단순한 BFS가 아니라 여러 조건을 고려해야 풀 수 있을 것이다.

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

public class Main {
    static char[][][] map = new char[9][8][8];
    static int[] dx = {0, -1, 1, 0, 0, 1, -1, 1, -1};
    static int[] dy = {0, 0, 0, -1, 1, 1, 1, -1, -1};
    static int ans = 0;

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

        for(int i=0; i<8; i++) {
            input = br.readLine();

            for(int j=0; j<8; j++) {
                map[0][i][j] = input.charAt(j);
            }
        }

        for(int i=1; i<9; i++) {
            move(i);
        }

        bfs();

        System.out.println(ans);
    }

    public static void bfs() {
        Queue<Pair> queue = new LinkedList<>();
        boolean[][] visited = new boolean[8][8];
        visited[7][0] = true;
        queue.add(new Pair(7, 0, 0));

        while(!queue.isEmpty()) {
            Pair temp = queue.poll();

            if(map[temp.t][temp.x][temp.y]=='#')
                continue;

            if(temp.x==0 && temp.y==7 || temp.t==8){
                ans = 1;
                return;
            }

            for(int i=0; i<9; i++) {
                int nx = temp.x + dx[i];
                int ny = temp.y + dy[i];
                int nt = temp.t + 1;

                if (i > 0) {
                    if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8 || visited[nx][ny] || map[temp.t][nx][ny] == '#')
                        continue;
                }

                if(nx>=1) {
                    if(map[temp.t][nx-1][ny] == '#')
                        continue;
                }

                visited[nx][ny] = true;
                queue.add(new Pair(nx, ny, nt));
            }
        }
    }

    public static void move(int z) {

        for(int i=7; i>=0; i--) {
            for(int j=0; j<8; j++) {
                if(i==0)
                    map[z][i][j]='.';

                else {
                    if(map[z-1][i-1][j]=='#')
                        map[z][i][j]='#';
                    else
                        map[z][i][j]='.';
                }
            }
        }
    }

    public static class Pair{
        int x;
        int y;
        int t;

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