문제

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

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

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

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

입력

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

출력

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

예제1 - 입력

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

예제1 - 출력

1

예제2 - 입력

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

예제2 - 출력

0

예제3 - 입력

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

예제3 - 출력

0

예제4 - 입력

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

예제4 - 출력

1

예제5 - 입력

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

예제5 - 출력

0

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Parameter;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static final int SIZE = 8;
    static int[] mx = {0, 0, -1, 1, -1, -1, 1, 1, 0};
    static int[] my = {-1, 1, 0, 0, -1, 1, 1, -1, 0};
    static char[][][] board;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        board = new char[SIZE][SIZE][SIZE];

        for (int i = 0; i < SIZE; i++) {
            char[] input = br.readLine().toCharArray();
            for (int j = 0; j < SIZE; j++) {
                board[0][i][j] = input[j];
            }
        }
        br.close();

        for (int step = 1; step < SIZE; step++) {
            for (int i = 0; i < SIZE - 1; i++) {
                for (int j = 0; j < SIZE; j++) {
                    board[step][i + 1][j] = board[step - 1][i][j];
                }
            }
            for (int i = 0; i < SIZE; i++) {
                board[step][0][i] = '.';
            }
        }

        if (dfs(new Pair(SIZE - 1, 0), 0))
            System.out.println(1);
        else
            System.out.println(0);
    }
    static boolean dfs(Pair now, int depth) {
        if (depth == SIZE - 1){ //8번이면 벽이 사라져서 무조건 성공
            return true;
        }
        if (now.x == 0 && now.y == SIZE - 1) {
            return true;
        }
        for (int i = 0; i < mx.length; i++) {
            int tx = now.x + mx[i];
            int ty = now.y + my[i];

            if (tx < 0 || tx >= SIZE || ty < 0 || ty >= SIZE)
                continue;

            if (board[depth][tx][ty] == '.' && board[depth + 1][tx][ty] == '.') {
                if (dfs(new Pair(tx, ty), depth + 1)) {
                    return true;
                }
            }
        }
        return false;
    }
    static class Pair {
        public int x;
        public int y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}