16954 움직이는 미로탈출

알고리즘(BFS)

1. q와 nextq를 선언
2. q엔 현재 노드를 저장. 하나식 꺼내서 이동가능한 인접 칸을 nextq에 추가.
3. 다 추가하면, 벽을 한칸 내림
4. 이후 q에 nextq를 넣고, nextq는 비운채 다음 루프 시작.
5. 루프 중에 q에서 꺼낸 노드가 벽이 있는 칸이라면 추가안하고 다음 노드로, 최우측상단이라면 종료

코드

#include <bits/stdc++.h>
 
using namespace std;
 
char miro[8][8];
list<pair<int, int>> q, nextq;
bool visitcheck[8][8];
 
bool BFS();
 
int main() {
	for (int i = 0; i < 8; i++)
		for (int j = 0; j < 8; j++)
			cin >> miro[i][j];
 
	cout << BFS();
}
 
bool BFS() {
	bool check = false;
	nextq.push_back({ 7,0 });
 
	while (!nextq.empty() && !check) {
		q = nextq;
		nextq.clear();
		memset(visitcheck, 0, sizeof(visitcheck));
 
		while (!q.empty()) {
			int r = q.front().first, c = q.front().second;
			q.pop_front();
 
			if (miro[r][c] == '#')
				continue;
			if (r == 0 && c == 7) {
				check = true;
				break;
			}
 
			if (miro[r][c] != '#' && !visitcheck[r][c]) {
				nextq.push_back({ r, c });
				visitcheck[r][c] = true;
			}
			if (r > 0 && miro[r - 1][c] != '#' && !visitcheck[r - 1][c]) {
				nextq.push_back({ r - 1,c });
				visitcheck[r - 1][c] = true;
			}
			if (r > 0 && c < 7 && miro[r - 1][c + 1] != '#' && !visitcheck[r - 1][c + 1]) {
				nextq.push_back({ r - 1,c + 1 });
				visitcheck[r - 1][c + 1] = true;
			}
			if (c < 7 && miro[r][c + 1] != '#' && !visitcheck[r][c + 1]) {
				nextq.push_back({ r, c + 1 });
				visitcheck[r][c + 1] = true;
			}
			if (r < 7 && c < 7 && miro[r + 1][c + 1] != '#' && !visitcheck[r + 1][c + 1]) {
				nextq.push_back({ r + 1,c + 1 });
				visitcheck[r + 1][c + 1] = true;
			}
			if (r < 7 && miro[r + 1][c] != '#' && !visitcheck[r + 1][c]) {
				nextq.push_back({ r + 1,c });
				visitcheck[r + 1][c] = true;
			}
			if (r < 7 && c > 0 && miro[r + 1][c - 1] != '#' && !visitcheck[r + 1][c - 1]) {
				nextq.push_back({ r + 1,c - 1 });
				visitcheck[r + 1][c - 1] = true;
			}
			if (c > 0 && miro[r][c - 1] != '#' && !visitcheck[r][c - 1]) {
				nextq.push_back({ r, c - 1 });
				visitcheck[r][c - 1] = true;
			}
			if (r > 0 && c > 0 && miro[r - 1][c - 1] != '#' && !visitcheck[r - 1][c - 1]) {
				nextq.push_back({ r - 1,c - 1 });
				visitcheck[r - 1][c - 1] = true;
			}
		}
 
		for (int i = 7; i > 1; i--)
			for (int j = 0; j < 8; j++)
				miro[i][j] = miro[i - 1][j];
		for (int j = 0; j < 8; j++)
			miro[0][j] = '.';
	}
 
	return check;
}