문제
욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다.
이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다.
1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.
욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보자.
입력
8개 줄에 걸쳐서 체스판의 상태가 주어진다. '.'은 빈 칸, '#'는 벽이다. 가장 왼쪽 아랫칸은 항상 벽이 아니다.
출력
욱제의 캐릭터가 가장 오른쪽 윗 칸에 도착할 수 있으면 1, 없으면 0을 출력한다.
예제 입력 1
........
........
........
........
........
........
........
........
예제 출력 1
1
예제 입력 2
........
........
........
........
........
........
##......
........
예제 출력 2
0
예제 입력 3
........
........
........
........
........
.#......
#.......
.#......
예제 출력 3
0
예제 입력 4
........
........
........
........
........
.#######
#.......
........
예제 출력 4
1
예제 입력 5
........
........
........
........
#.......
.#######
#.......
........
예제 출력 5
0
풀이
예제 3을 본다면
........
........
........
........
........
.#......
#.......
*#......
........
........
........
........
........
.#......
#*......
.#......
........
........
........
........
........
.#......
-> *가 #에 부딪쳐 탈출 실패
예제 4
........
........
........
........
........
.#######
#.......
*.......
........
........
........
........
........
.#######
#.......
.*......
........
........
........
........
........
.#######
#*......
........
........
........
........
........
*#######
#.......
........
........
........
........
*.......
.#######
........
........
........
.*......
........
.
.
->탈출 성공
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[][] graph;
public static final int[] dx = { 1, -1, 0, 0, -1, -1, 1, 1, 0 };
public static final int[] dy = { 0, 0, 1, -1, -1, 1, 1, -1, 0 };
static int N;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
N = 8;
graph = new char[N][N];
boolean[][][] check = new boolean[8][8][9];
check[7][0][0] = true;
for (int i = 0; i < N; i++) {
String s = reader.readLine();
for (int j = 0; j < N; j++)
graph[i][j] = s.charAt(j);
}
Queue<Integer> q = new LinkedList<Integer>();
q.add(7); q.add(0); q.add(0);
boolean ans = false;
while (!q.isEmpty()) {
int x = q.remove();
int y = q.remove();
int t = q.remove();
if (x == 0 && y == 7) ans = true; //오른쪽 맨 위에 도착할 경우
for (int k = 0; k < 9; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
int nt = Math.min(t+1, 8);
if (nx < 0 || nx >= N || ny < 0 || ny >= N)
continue;
if (nx-t >= 0 && graph[nx-t][ny] == '#') continue;
//nx-t >= 0 t초 후에 행이 0보다 크거나 같을경우(현재 칸)
if (nx-t-1 >= 0 && graph[nx-t-1][ny] == '#') continue;
//nx-t-1(미래칸)
if (check[nx][ny][nt] == false) {
check[nx][ny][nt] = true;
q.add(nx); q.add(ny); q.add(nt);
}
}
}
System.out.println(ans ? 1 : 0);
}
}
