16954번 움직이는 미로 탈출

지난 번, DFS를 사용할 때(재귀)map이 계속해서 바뀌면 벡터 그대로 함수에 넣어주라고 말한적이 있다. 하지만 여기서는 BFS를 사용하겠다.
키 포인트는 캐릭터가 이동하고 나서 map을 한 칸 내릴텐데, 언제 Q에 넣고, 언제 map을 내리는지가 중요하다.

BFS의 queue에서 내가 주의할 점!!!

queue에서 하나를 뺄 때 dx,dy를 돌면서 다시 queue에 넣어준다. 이때 내가 간과한 것이 같은 레벨인 queue(예를 들어 1,2,2,3,3,3,4,4,4,4의 queue에서 각각의 레벨)를 다 꺼내지 않고 레벨을 올린다. 즉 1을 꺼내고 2,2을 넣고, 2를 하나만 빼고 3,3,3을 채운다. 이렇게 해서 실패하였다.
아래는 오류 코드이다.(백준 87%에서 멈춤). 이런 생각은 절대 하면 안된다!!

#include <iostream>
#include <queue>
using namespace std;

char map[8][8];
int ch[8][8];
int dx[9] = { -1,0,1,0,-1,1,1,-1,0 };
int dy[9] = { 0,1,0,-1,1,1,-1,-1,0 };
void f() {
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			cout << map[i][j];
		}
		cout << '\n';
	}
}
struct Loc {
	int x, y;
	Loc(int a, int b) {
		x = a;
		y = b;
	}
};
int main() {
	//freopen("in1.txt", "rt", stdin);
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			cin >> map[i][j];
		}
	}

	queue<Loc> Q;
	Q.push(Loc(7, 0));
	for (int k = 0; k < 8; k++) { //총 8번의 시련을 견디면 성공
		//if (k == 1) f();
		if (Q.empty()) {
			cout << "0" << '\n';
			return 0;
		}
		Loc tmp = Q.front();
		Q.pop();
		
		if (map[tmp.x][tmp.y] == '.') {
			for (int i = 0; i < 9; i++) { //방향
				int xx = tmp.x + dx[i];
				int yy = tmp.y + dy[i];
				if (xx >= 8 || xx < 0 || yy>=8 || yy < 0) continue;
				if (xx-1>=0&&map[xx][yy] == '.' && map[xx-1][yy]=='.') Q.push(Loc(xx, yy));
			}
		}
		for (int a = 7; a >= 1; a--) {
			for (int b = 0; b < 8; b++) {
				map[a][b] = map[a - 1][b];
			}
		}
		for (int a = 0; a < 8; a++) {
			map[0][a] = '.';
		}

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

따라서 BFS를 사용할 때는 정확히 레벨을 지켜줄 필요가 있다. 앞으로도 유의해야 겠다 꼭!!!!!
여기서는 시간 t를 이용해서 BFS의 레벨을 계속해서 유지하였다. 기억하자!

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

char map[8][8];
int ch[8][8][9];
int dx[9] = { -1,0,1,0,-1,1,1,-1,0 };
int dy[9] = { 0,1,0,-1,1,1,-1,-1,0 };
void f() {
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			cout << map[i][j];
		}
		cout << '\n';
	}
}
struct Loc {
	int x, y, z;
	Loc(int a, int b, int c) {
		x = a;
		y = b;
		z = c;
	}
};
int main() {
	int ans = 0;
	//freopen("in1.txt", "rt", stdin);
	for (int i = 0; i < 8; i++) {
			cin >> map[i];
		
	}
	queue<Loc> Q;
	Q.push(Loc(7, 0, 0));
	while (!Q.empty()) {
		//if (k == 1) f();
		Loc tmp = Q.front();
		Q.pop();
		if (tmp.x == 0 && tmp.y == 7) {
			ans = 1;
			break;
		}
		
		for (int i = 0; i < 9; i++) { //방향
			int xx = tmp.x + dx[i];
			int yy = tmp.y + dy[i];
			int t = min(tmp.z + 1, 10);
			if (xx >= 8 || xx < 0 || yy >= 8 || yy < 0) continue;
			if (xx-tmp.z>=0&&map[xx-tmp.z][yy] == '#') continue;
			if (xx - tmp.z-1 >= 0 && map[xx - tmp.z-1][yy] == '#') continue;
			if (ch[xx][yy][t]==0) {
				ch[xx][yy][t] = 1;
				Q.push(Loc(xx, yy, t));
			}
			
		}
	}
	cout << ans << '\n';
	return 0;
}