백준16594 - 움직이는 미로 탈출

https://www.acmicpc.net/problem/16954

16954번: 움직이는 미로 탈출

bfs를 변형시킨 문제였다.

 

입력 시 벽의 위치를 큐에 저장하여 1초 단위로 벽이 (x, y)에 z초에 도달한 경우를 true로 체크해준다.

 

탈출구를 찾는 과정은 이동하려는 위치에 벽이 존재하거나 이동한 뒤에 바로 벽이 내려오는 경우는 경로 찾기에서 제외한 상하좌우, 대각선, 제자리 이동하는 경우를 큐에 넣어서 탐색을 진행한다. 어느 한 점에서 9초 이상이라면 벽이 모두 사라졌으므로 무조건 탈출이 가능하다.

#include <iostream>
#include <queue>
#define MAX 10 //9초가 되야 탈출할 가능성이 100프로라서 MAX를 100으로 설정
using namespace std;

//(x, y)까지 z초가 걸림
class Point {
public:
	int x, y, z;
	Point(int x, int y, int z) {
		this->x = x;
		this->y = y;
		this->z = z;
	}
};

bool wallvisit[MAX][MAX][MAX] = { false, }; //(x, y)를 z초에 방문한 벽을 체크
queue<Point> wall; //벽이 (x, y)에 존재하고 그 순간이 z초일 때를 저장
char mat[MAX][MAX]; //좌표 정보

//상하좌우, 대각선, 제자리
int dx[] = { 1,-1,0,0,1,1,-1,-1,0};
int dy[] = { 0,0,1,-1,1,-1,1,-1,0};

int find(int x, int y, int z) {
	queue<Point> q;
	q.push(Point(x, y, z));
	
	while (!q.empty()) {
		x = q.front().x;
		y = q.front().y;
		z = q.front().z;
		q.pop();

		if (z > 8) {
			return 1;
		}

		for (int i = 0; i < 9; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (1 <= nx && nx <= 8 && 1 <= ny && ny <= 8) {
				if (!wallvisit[nx][ny][z] && !wallvisit[nx][ny][z + 1]) { //도달하려는 위치와 같은 시간에 벽이 오지 않는 경우와 도달하려는 위치에 도달한 후 벽이 오지 않는 경우
					q.push(Point(nx, ny, z + 1)); //다음 위치를 큐에 삽입
				}
			}
		}
	}

	return 0; //도착지로 못간 경우 0 반환
}

int main() {
	for (int i = 1; i <= 8; i++) {
		for (int j = 1; j <= 8; j++) {
			cin >> mat[i][j];
			if (mat[i][j] == '#') {
				wall.push(Point(i, j, 0));
			}
		}
	}

	//벽을 한 칸씩 밑으로 내림, 좌표 범위 밖이면 삭제
	while (!wall.empty()) {
		int x = wall.front().x;
		int y = wall.front().y;
		int z = wall.front().z;
		wallvisit[x][y][z] = true;
		wall.pop();

		if (1 <= x + 1 && x + 1 <= 8) {
			wall.push(Point(x + 1, y, z + 1));
		}
	}

	cout << find(8, 1, 0);
}