[백준 3055] 탈출

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

3055번: 탈출

#include <cstdio>
#include <cstring>
#include <queue>
int R, C;
char in[50 + 2][50 + 2];
int board[50 + 2][50 + 2];

int sx, sy;	// 시작위치 
struct _st
{
	int flag;	// 물: 2, 고슴도치: 3
	int x, y;
	int time;
};
std::queue<_st> Q;
int visited[50 + 2][50 + 2];

void input()
{
	scanf("%d %d", &R, &C);
	for (int r = 0; r < R; r++) {
		scanf("%s", &in[r]);
		for (int c = 0; c < C; c++) {
			if (in[r][c] == '.') board[r][c] = 0;
			else if (in[r][c] == '*') {
				board[r][c] = 2;
				Q.push({ 2, r, c });
				visited[r][c] = 1;
			}
			else if (in[r][c] == 'X') board[r][c] = 1;
			else if (in[r][c] == 'D') board[r][c] = 3;
			else if (in[r][c] == 'S') {
				board[r][c] = 0;
				sx = r, sy = c;
			}
		}
	}
	Q.push({ 3, sx, sy });
	visited[sx][sy] = 1;
}


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

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

		if (data.flag == 3 && board[data.x][data.y] == 3) return data.time;

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

			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
			if (visited[nx][ny]) continue;
			if (board[nx][ny] == 1) continue;
			if (data.flag == 2 && board[nx][ny] == 3) continue;
			Q.push({ data.flag, nx, ny, data.time + 1 });
			visited[nx][ny] = 1;
		}
	}
	return -1;
}




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

1. 이 문제의 핵심은 다음 문장이다. 

"고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. " 

=> 큐는 FIFO 자료구조이다. 따라서 board를 input 받으면서 물에 대한 좌표를 먼저 큐에 모두 삽입하고, 가장 나중에 고슴도치의 좌표를 큐에 삽입하면 "물 이동 -> 고슴도치 이동"이 자연스럽게 구현된다. 

 

 

2. 물은 비버굴에 도달할 수 없지만, 고슴도치가 탈출하려면 비버굴에 도달해야 한다. 

현재 큐에서 pop된 좌표가 물의 이동 좌표인지, 고슴도치가 이동하는 좌표인지 구분하기 위해 flag를 두었다. 물이면 다음 이동좌표 (nx, ny)가 비버굴이면 방문하지 않고 스루한다.