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

문제

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

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

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

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

입력

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

출력

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

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,-1,0,1,1,1,0,-1,0 }, dx[] = { 0,1,1,1,0,-1,-1,-1,0 }, INF = 987654321;

using namespace std;
int mp[81][9][9];
char c;
int v[81][9][9];
int main() {
	FAST;
	REP(i, 8)REP(j, 8) {
		cin >> c;
		if (c == '#')
			mp[0][i][j] = 1;
	}
	REP(i, 8)REP(j, 8) {
		if (mp[0][i][j] == 1) {
			REP(k, 81) {
				int ny = i + k;
				if (ny <= 8)mp[k][ny][j] = 1;
			}
		}
	}
	queue<ti>q;
	q.push({ 0,8,1 });
	v[0][8][1] = 1;
	while (!q.empty()) {
		auto [k, y, x] = q.front();
		q.pop();

		rep(i,9){
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= 1 && ny <= 8 && nx >= 1 && nx <= 8 && !mp[k][ny][nx] && !mp[k + 1][ny][nx] && !v[k + 1][ny][nx]) {
				q.push({ k + 1,ny,nx });
				v[k + 1][ny][nx] = 1;
				if (ny == 1 && nx == 8) {
					cout << 1;
					return 0;
				}
			}
		}
	}
	cout << 0;
}

BFS문제입니다.

벽이 1초마다 한칸씩 내려오고, 욱제는 가만히 있는거 포함, 상하좌우 대각선으로 이동이 가능합니다.

따라서 현재 위치 기준으로 이동할 지점에 벽이 있거나, 이동할 위치 기준으로 다음 시간에 벽이 있다면 이동이 불가능 합니다.