백준 16954. 움직이는 미로 탈출

알고리즘 중급 문제 중 611 - BFS(연습)

움직이는 미로 탈출

BFS와 시뮬레이션을 결합한 문제

1. 간단 설명

---

8*8 지도에서 가장 왼쪽 아래칸(7,0)에서 오른쪽 위칸(0,7)으로 이동해야한다

그런데 1초마다 모든 벽이 위에서 아래로 한칸씩 내려간다

가장 아래 행에 도달하면 해당 열은 다음턴에 사라진다

목적지에 도달할 수 있다면 1을, 아니라면 0을 출력하는 프로그램

2. 예시

---

이런식으로 쓸려 내려간다. 폴가이즈같이

예제1)

벽에 밀려서 장외로 도달 불가!

예제2)

(6,1)에서 캐릭터가 벽에 끼어버려서 불가!

BFS 탐색에서 이동이 가능하더라도, 다음턴에 벽에 끼어버리는 경우도 있다

예제 3)

벽을 피해서 도달 가능!

예제 4)

시작할 때, 움직이지 않고 대기하면 도달 가능하다

3. 알고리즘

---

1. 맵을 입력받고 시작지점에서 BFS를 시작한다
- BFS 시작 시 시작 좌표를 visited 처리해버리면, 대기하는 경우를 처리하지 못해 실패함
2. BFS 시작
	2-1. 꺼낸 좌표가 목적지라면, 혹은 8초가 경과해서 맵에 벽이 없다면, 1을 리턴
	2-2. 아니라면 9방향으로 탐색 시도
	2-3. 맵 밖으로 나갔다면 패스
	2-4. 다음 이동하려는 칸이 벽이라면 패스
	2-5. 다음 이동하려는 칸에 벽이 내려온다면 패스
	2-6. 방문한적이 없다면 이 좌표와 초를 큐에 넣는다  

4. 소스코드

---

#include <iostream>
#include <string>
#include <queue>

using namespace std;

string map[8];
bool visited[8][8][9];
int direct[9][2] = {
	{-1,-1},
	{-1,0},
	{-1,1},
	{0,1},
	{1,1},
	{1,0},
	{1,-1},
	{0,-1},
	{0,0},
};

struct Pos {
	int y;
	int x;
	int time;
};

void Input() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	
	for (int i = 0; i < 8; i++) {
		cin >> map[i];
	}
}

int main() {
	Input();

	queue<Pos> qu;
	qu.push({ 7,0,0 }); // 시작지점 (7,0)과 0초 넣기
	// visited[7][0][0] = true;

	int result = 0;
	while (!qu.empty()) {
		auto [y, x, time] = qu.front();
		qu.pop();

		if ((y == 0 && x == 7) || (time >= 8)) { // 목적지에 도달했거나, 8초를 넘었다면
			result = 1;
			break;
		}

		for (int t = 0; t < 9; t++) {
			int dy = direct[t][0] + y;
			int dx = direct[t][1] + x;
			int dt = time + 1;

			if (dy < 0 || dx < 0 || dy >= 8 || dx >= 8) continue; // 맵밖
			/***가장 중요한 부분***/
			if (dy - time >= 0 && map[dy - time][dx] == '#') continue; // 가려는 칸에 벽이 있다면
			if (dy - time - 1 >= 0 && map[dy - time - 1][dx] == '#') continue; // 가려는 칸이 내려오는 벽과 겹칠때
			/********************/

			// 방문한적 없다면
			if (!visited[dy][dx][time]) {
				visited[dy][dx][time] = true;
				qu.push({ dy, dx, dt });
			}
		}
	}
	cout << result;

	return 0;
}

문제 이해도 어려웠을 뿐더러, 알고리즘도 어려웠던 문제

한시간 고민하다가 답을 보고 해결했다

1. BFS로 이동할 수 있더라도, 1초 경과 후 벽에 끼는 경우도 존재한다

2. 시작 시 visited를 처리해버리면, 시작하면서 대기하는 경우 처리가 안된다. 이를 주의할 것!

3. 어짜피 벽이 내려오면 아래로 내려갈 일은 없으므로, ←↖↑↗→ + 대기 만 구현하면 되지 않을까? 싶어서 시도했으나 실패. 아래로 내려가야하는 케이스도 존재하는 것 같다