[백준 16954] 움직이는 미로 탈출

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

16954번: 움직이는 미로 탈출

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
char board[8 + 2][8 + 2];
char tmp[8 + 2][8 + 2];

struct _st
{
	int x, y;
};
std::queue<_st> Q;
int visited[8 + 2][8 + 2];
std::vector<_st> V;

void input()
{
	for (int i = 0; i < 8; i++) {
		scanf("%s", &board[i]);
		for (int j = 0; j < 8; j++) {
			if (board[i][j] == '#') V.push_back({ i, j });
		}
	} 
	Q.push({ 7, 0 });
	visited[7][0] = 1;
}

int BFS()
{
	int dir_x[8] = { 1, 1, 1, 0, 0, -1, -1 ,-1};
	int dir_y[8] = { 0, -1, 1, -1, 1, 0, -1, 1 };

	if (Q.empty()) return 0;	// 더이상 못감

	memset(visited, 0, sizeof(visited));
	std::queue<_st> Buffer;

	while (!Q.empty()){
		_st data = Q.front();
		//printf("%d %d\n", Q.front());
		Q.pop();

		if (data.x == 0 && data.y == 7) return 1;	// 목표지점에 도달함
		if (board[data.x][data.y] == '#') continue;

		for (int p = 0; p < 8; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > 7 || ny < 0 || ny > 7) continue;
			if (visited[nx][ny]) continue;
			if (board[nx][ny] == '#') continue;

			Buffer.push({ nx, ny });
			visited[nx][ny] = 1;
		}
		Buffer.push({ data.x, data.y });	// 가만히 있을 수 도 있다. 
		visited[data.x][data.y] = 1;
	}
	Q = Buffer;
	return 2;	// 더이상 못감
}


void move_wall()
{
	std::vector<_st> Buffer;

	//init tmp
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			tmp[i][j] = '.';
		}
	}
	
	if (V.empty()) {
		memcpy(board, tmp, sizeof(tmp));
		return;
	}

	for (_st data : V) {
		int nx = data.x + 1;
		int ny = data.y;
		if (nx > 7) continue;
		tmp[nx][ny] = '#';
		Buffer.push_back({ nx ,ny });
	}

	memcpy(board, tmp, sizeof(tmp));
	V.clear();
	V = Buffer;
}

bool simul()
{
	while (1) {
		int res = BFS();
		if (res == 0) return false;	// 큐에 아무것도 없을 때 
		if (res == 1) return true;	// 목표 지점에 도착했을 때 
		move_wall();
		//debug();
	}
}

int main()
{
	input();
	bool ans = simul();
	printf("%d\n", ans);
	return 0;
}

1. 방문처리 때문에 {0, 0}까지 넣어서 방향 벡터 만들어도 "제 자리에 가만히 있을 수 도 있다"는 케이스를 처리해주지 못한다. 문제에서 이런 조건이 있으면 (nx, ny)를 구하기 위해 방향 벡터를 돌리는 루프 "밖에서" 현재 좌표를 큐에 직접 push해 주도록 하자 !

2. 잘못된 생각(벽이 내려오기도 하고, 어차피 (0, 7)로 가야하니까 이전 좌표는 방문하지 않지 않을까 하는,,) 때문에 방문배열 초기화를 안해줬었는데 음 이런 생각 잘못된 생각... 

벽이 내려오면서 맵의 상태가 달라지기 때문에, 욱제가 갈 수있는 좌표 또한 달라진다. 따라서 방문배열을 초기화해주면서 BFS 돌려주어야 한다.