[백준 3055] 탈출

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

3055번: 탈출

#include <cstdio>
#include <queue>
int R, C;
char forest[50 + 2][50 + 2];
int visited[50 + 2][50 + 2];

struct _st
{
	int type;	// 홍수 -1 고슴도치 1
	int x;
	int y;
	int cnt;
};
int dx, dy;	// 비버굴
int sx, sy;	// 고슴도치 위치


std::queue<_st> Q;

void input()
{
	scanf("%d %d", &R, &C);
	for (int i = 0; i < R; i++) {
		scanf("%s", &forest[i]);
		for (int j = 0; j < C; j++) {
			if (forest[i][j] == '*') Q.push({ -1, i, j, 0 });	// 홍수가 일어날 수 있는 모든 좌표를 저장한다. 
			else if (forest[i][j] == 'D') {
				dx = i; dy = j;
			}
			else if (forest[i][j] == 'S') {
				sx = i; sy = j;
			}
		}
	}
	Q.push({ 1, sx, sy, 0 });
}

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


	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

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

			if (data.type == 1 && data.x == dx && data.y == dy) return data.cnt;

			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;		// 영역을 벗어났다면 스루
			if (forest[nx][ny] == 'X') continue;	// 벽을 만났다면 스루
			if (visited[nx][ny]) continue;			// 방문했다면 스루

			switch (data.type) {
			case -1:
				if (forest[nx][ny] == 'D') continue;
				visited[nx][ny] = -1;
				Q.push({ -1, nx, ny, 0 });
				break;
			case 1:
				if (forest[nx][ny] == '*') continue;
				visited[nx][ny] = 1;
				Q.push({ 1, nx, ny, data.cnt + 1 });
				break;

			}
		}
	}
	return -1;
}


int main()
{
	input();
	int ans = BFS();
	if (ans == -1) printf("KAKTUS");
	else printf("%d\n", ans);
	return 0;
}

이 문제의 key는 "고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다"는 것이다. 즉, 다음 상태발전에서 물이 찰 예정인 칸으로는 고슴도치는 이동할 수 없다. 따라서 1. 물이 찰 예정인 지역을 모두 방문 표시 후 2. 고슴도치를 움직여야 한다. 

이를 위해 물이 차 있는 지역을 우선적으로 큐에 삽입하고, 가장 마지막에 고슴도치의 위치를 삽입해야 한다. 

 

이렇게 데이터를 받으면 BFS 함수에서 상태발전 시, 물이 차 있는 지역에 대한 좌표가 먼저 pop된다. 즉 고슴도치가 움직이기 전에 물이 찰 예정인 지역을 모두 방문하여 표시를 해주면 다음으로 고슴도치의 좌표가 pop되어 상태발전을 할 때 해당 좌표를 거를 수 있다. 

 

 

그리고 nx, ny... 영역 확인할 때 변수 실수좀 하지마라...