[C++] 백준 16954번: 움직이는 미로 탈출

문제 링크

16954번: 움직이는 미로 탈출

문제 요약

욱제가 왼쪽 아래 칸에서 오른쪽 위 칸으로 이동한다. 욱제가 이동한 뒤에는 체스 칸의 모든 벽이 아래로 한 칸씩 이동한다. 이때, 욱제가 오른쪽 위 칸으로 이동할 수 있는지 알아내야 한다. 욱제는 인접한 모든 한 칸으로 이동하거나, 현재 자리에 가만히 있을 수 있다. 만약 욱제가 있는 자리에 벽이 내려오게 된다면, 욱제는 더 이상 이동할 수 없다.

접근 방법

체스판은 덱을 이용해서 구현하면 편리합니다. 덱은 인덱스 접근이 허용되기 때문에 덱에 string을 저장하는 식으로 체스판을 구현했습니다.

기본적으로 구조체를 만들어서 현재 위치와 이동 횟수를 저장하고, BFS를 돌렸습니다. 벽의 이동 횟수도 별도로 카운트 해주는데, 만약 현재 이동 횟수가 벽의 이동횟수보다 커지면 바로 벽을 이동시킵니다. 덱을 pop_back() 해주고, front에 "........"을 문자열로 넣어주면 됩니다.

BFS를 돌릴 때, 벽이 이동하면서 상태가 변하기 때문에, 칸에 대한 재방문은 허용하되, 큐의 크기가 너무 커질 수 있기 때문에 이동 횟수가 동일할 때 같은 칸을 재방문 하는 경우는 막아주었습니다. 재방문에 대한 처리는 set으로 구현했습니다. set에 구조체를 넣고, 구조체에서 연산자 오버로딩을 했습니다.

BFS 도중에, 목적지에 도달하면 종료해줘야 합니다. 만약, 현재 위치에 벽이 내려오면 continue를 해줘야 합니다. 이 외의 구현은 일반적인 BFS와 크게 다르지 않습니다.

코드

#include <bits/stdc++.h>

using namespace std;

struct Data {
	int r, c, cnt;

	bool operator<(const Data& a) const {
		if (r == a.r) {
			if (c == a.c)
				return cnt < a.cnt;
			return c < a.c;
		}
		return r < a.r;
	}
};

set<Data> visited;

int main(void) {
	deque<string> dq;
	for (int i = 0; i < 8; i++) {
		string tmp;
		cin >> tmp;
		dq.push_back(tmp);
	}

	int cnt = 0;
	queue<Data> q;
	q.push({ 7, 0, 0 });
	visited.insert({ 7, 0, 0 });

	while (!q.empty()) {
		auto now = q.front();
		q.pop();

		if (now.r == 0 && now.c == 7) {
			cout << 1 << '\n';
			return 0;
		}

		if (cnt + 1 == now.cnt) {
			cnt++;
			dq.pop_back();
			dq.push_front("........");
		}

		if (dq[now.r][now.c] == '#')
			continue;

		for (int i = -1; i <= 1; i++) {
			for (int j = -1; j <= 1; j++) {
				Data next = { now.r + i, now.c + j, now.cnt + 1 };
				if (next.r >= 0 && next.c >= 0 && next.r < 8 && next.c < 8
					&& visited.find(next) == visited.end() && dq[next.r][next.c] == '.') {
					visited.insert(next);
					q.push(next);
				}
			}
		}
	}

	cout << 0 << '\n';
	return 0;
}