방과후
ALGORITHM NOTE약 2분

BOJ 16954 - 움직이는 미로 탈출

8초만 버텨!!!

#algorithm#boj#gold#bfs#grid
아카이브로 돌아가기

문제 링크

문제

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

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

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

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

입력

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

출력

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

풀이

이 문제는 위치만으로는 상태를 표현할 수 없고, 시간까지 같이 봐야 한다. 같은 칸이라도 몇 초 뒤에 도착했느냐에 따라 벽 위치가 달라지기 때문이다.

코드에서는 (x, y, t) 상태로 BFS를 돌린다. 현재 시간 t에 그 칸이 벽이 아니고, 다음 시간 t+1에도 벽이 아니어야만 이동 가능하다. 이 조건을 isNotWall()에서 검사한다.

벽은 최대 8초가 지나면 모두 사라지므로, t >= 8에 도달하면 사실상 탈출 성공으로 볼 수 있다.

또한 이 문제에서는 제자리 대기도 가능하므로, 이동 방향 8개에 현재 위치 유지까지 포함해서 총 9가지 선택을 본다. 지금은 안전해 보여도 다음 초에 벽이 내려와 부딪히는 경우가 있으니, 현재 칸과 다음 칸을 함께 검사해야 한다.

격자 크기가 8 x 8로 작아서 시간 차원까지 포함해도 상태 수가 많지 않다. 결국 움직이는 미로를 "시간에 따라 변하는 그래프"로 보고 BFS를 돌리는 문제라고 정리할 수 있다.

코드

cpp
#include <iostream>
#include <string>
#include <queue>
using namespace std;
 
char graph[8][8];
bool visited[8][8][9];
int dx[] = {0, 1, 0, -1, 0, 1, 1, -1, -1};
int dy[] = {0, 0, 1, 0, -1, 1, -1, 1, -1};
 
struct State {
    int x, y, t;
};
 
bool isNotWall(int x, int y, int t) {
    if (x - t >= 0 && graph[x - t][y] == '#') return false;
    if (x - (t + 1) >= 0 && graph[x - (t + 1)][y] == '#') return false;
    return true; 
}
 
bool isInRange(int x, int y) {
	return (x >= 0 && y >= 0 && x < 8 && y < 8);
}
 
int solve() {
    queue<State> q;
	q.push({7, 0, 0});
    visited[7][0][0] = true;
 
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
        int t = q.front().t;
		q.pop();
 
		if ((x == 0 && y == 7) || t >= 8)
			return 1;
 
        for (int i = 0; i < 9; i++) {
    		int nx = x + dx[i];
	    	int ny = y + dy[i];
			int nt = t + 1;
 
		    if (isInRange(nx, ny) && isNotWall(nx, ny, t) && !visited[nx][ny][nt]) {
			    visited[nx][ny][nt] = true;
			    q.push({nx, ny, nt});
		    }
	    }
 
	}
 
	return 0;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	for (int i = 0; i < 8; i++) {
		string input;
		cin >> input;
 
		for (int j = 0; j < 8; j++) {
			graph[i][j] = input[j];
		}
	}
	
	cout << solve() << '\n';
	return 0;
}

복잡도

  • 시간 복잡도: O(8⋅8⋅9⋅9)O(8 \cdot 8 \cdot 9 \cdot 9)
  • 공간 복잡도: O(8⋅8⋅9)O(8 \cdot 8 \cdot 9)

마무리

움직이는 벽 때문에 시간 축이 반드시 필요하다. 하지만 격자가 작고 벽도 금방 사라져서, 시간까지 포함한 BFS로 충분히 해결된다.