문제
https://www.acmicpc.net/problem/16954
욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다.
이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다.
1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.
욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보자.
입력
8개 줄에 걸쳐서 체스판의 상태가 주어진다. '.'은 빈 칸, '#'는 벽이다. 가장 왼쪽 아랫칸은 항상 벽이 아니다.
출력
욱제의 캐릭터가 가장 오른쪽 윗 칸에 도착할 수 있으면 1, 없으면 0을 출력한다.
풀이
접근방법
시간제한 2초, 메모리 512MB이다.
체스판의 크기가 8x8이므로 시간과 메모리가 넉넉하다.
BFS로 접근해보자.
문제에서 정리할 수 있는 항목을 먼저 정리해보자.
1. 캐릭터가 먼저 이동하고, 그 다음 모든 벽들이 한 칸씩 아래로 간다.
2. 캐릭터는 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다.
즉 9가지 방향으로 이동가능.
3. 캐릭터와 벽이 겹치게 된다면, 캐릭터는 이동할 수 없다.코드로 구현 한다면 어떻게 구현할 수 있을까.
1. 캐릭터를 시작점에 둔다.
2. 캐릭터가 이동할 수 있는위치를 큐에 넣는다.
a. 캐릭터가 현재 벽과 겹쳐있는가?
b. 캐릭터가 도착지점에 도착하였는가?
3. 벽을 모두 한 칸씩 아래로 이동시킨다.를 고려하여 구현한다.
- 주의할 점
BFS를 수행시 방문체크가 필요하다.
방문 체크의 경우, 각 턴마다 확인을 해야한다.
-> 각 턴마다 벽이 내려오므로, 같은 위치라도 턴이 다르면 다른 경우이다.
여기서 BFS를 수행하면서, Depth관리를 어떻게 할 수 있을까
아래 코드와 같이 Queue를 2개 활용하면, 각 depth 별로 관리할 수 있다.
while (!q.isEmpty()) { // 전체 큐가 비었는가?
int size = q.size(); // 현재 큐의 사이즈 만큼만 수행한다. ( 같은 Depth )
while (size-- > 0) {
// 여기서 큐에 데이터가 삽입되더라도, 이미 위에서 몇 개를 수행할 지 계산하였음.
// something
}
}
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
public class Main {
static class Point {
int x;
int y;
Point(int a, int b) {
x = a;
y = b;
}
}
final static char BLANK = '.';
final static char WALL = '#';
final static int SIZE = 8;
static int[] dx = {0, -1, -1, -1, 0, 1, 1, 1, 0};
static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1, 0};
static char[][] map;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
map = new char[SIZE][SIZE];
// 입력
for (int i = 0; i < SIZE; ++i)
map[i] = in.readLine().toCharArray();
Queue<Point> q = new ArrayDeque<>(); // 캐릭터의 위치만 관리한다.
q.add(new Point(SIZE - 1, 0)); // 좌측 하단에서 시작
while (!q.isEmpty()) {
int size = q.size();
boolean visit[][] = new boolean[SIZE][SIZE];
while (size-- > 0) {
Point p = q.poll();
if(p.x == 0 && p.y == SIZE-1){ // 도착지에 도착
System.out.println(1);
return;
}
if (map[p.x][p.y] == BLANK) {
for (int d = 0; d < 9; ++d) {
int nextX = p.x + dx[d];
int nextY = p.y + dy[d];
if (isInRange(nextX, nextY) && visit[nextX][nextY] == false && map[nextX][nextY] == BLANK) {
visit[nextX][nextY] = true;
q.add(new Point(nextX, nextY));
}
}
}
}
// 캐릭터의 이동이 모두 완료됨.
// 벽을 내려보자.
moveWalls();
}
System.out.println(0);
}
private static void moveWalls() {
for (int i = SIZE - 2; i >= 0; --i) {
for (int j = 0; j < SIZE; ++j) {
map[i + 1][j] = map[i][j];
}
}
for (int i = 0; i < SIZE; ++i) {
map[0][i] = BLANK;
}
}
private static boolean isInRange(int x, int y) {
if (0 <= x && x < SIZE && 0 <= y && y < SIZE)
return true;
return false;
}
}
