[백준] 3055번 탈출

3055번: 탈출

백준 불 문제와 비슷한 문제이다.

모든 홍수 먼저 인접한 빈 곳을 찾아 *로 바꾸어주고

다음 검사를 위해 큐에 넣어준다.

그다음 고슴도치가 갈 수 있는 인접한 빈 곳을 찾아

그곳까지 가는데 걸린 시간 + 1을 넣어준다.

 

고슴도치가 D를 만나면 그때까지의 시간을 출력해주고

만나지 못했다면 KAKTUS를 출력한다.

#include <iostream>
#include <string>
#include <queue>
using namespace std;
char forest[51][51];
queue <pair<int, int>> flood, hedgehog, temp;
int Dx, Dy, success = -1, x, y;
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 }, visited[51][51] = { 0 }, res[51][51] = { 0 };

void Bfs(int R, int C) {
	while (1) {
		while (!flood.empty()) {
			for (int i = 0; i < 4; i++) {
				x = flood.front().first + dx[i], y = flood.front().second + dy[i];
				if (x >= 0 && x < R && y >= 0 && y < C && (forest[x][y] == '.' || forest[x][y] == 'S')) {
					forest[x][y] = '*';
					temp.push(pair<int, int>(x, y));
				}
			}
			flood.pop();
		}
		while (!temp.empty()) {
			flood.push(pair<int, int>(temp.front().first, temp.front().second));
			temp.pop();
		}
		while (!hedgehog.empty()) {
			for (int i = 0; i < 4; i++) {
				x = hedgehog.front().first + dx[i], y = hedgehog.front().second + dy[i];
				if (x >= 0 && x < R && y >= 0 && y < C && (forest[x][y] == '.' || forest[x][y] == 'D') && visited[x][y] == 0) {
					visited[x][y] = 1;
					res[x][y] = res[hedgehog.front().first][hedgehog.front().second] + 1;
					if (forest[x][y] == 'D') {
						success = res[x][y];
						break;
					}
					temp.push(pair<int, int>(x, y));
				}
			}
			hedgehog.pop();
			if (success != -1) break;
		}
		if (success != -1 || temp.empty()) break;
		while (!temp.empty()) {
			hedgehog.push(pair<int, int>(temp.front().first, temp.front().second));
			temp.pop();
		}
	}
}

int main() {
	int R, C;
	cin >> R >> C;
	string a;
	for (int i = 0; i < R; i++) {
		cin >> a;
		for (int j = 0; j < C; j++) {
			forest[i][j] = a[j];
			if (a[j] == 'S') hedgehog.push(pair<int, int>(i, j));
			else if (a[j] == 'D') Dx = i, Dy = j;
			else if (a[j] == '*') flood.push(pair<int, int>(i, j));
		}
	}

	Bfs(R, C);
	if (success == -1) cout << "KAKTUS\n";
	else cout << success;

	return 0;
}