백준 5427번 불 // C++

문제

 

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

 

---

 

풀이

 

1초가 지나면 다음과 같은 일이 일어난다.

• 불이 인접한 빈 공간으로 퍼져나간다.
• 상근이가 불이 나지 않은 곳으로 이동한다.

이 때, 상근이는 불이 날 곳으로 이동할 수 없다. 따라서 불을 먼저 이동시킨 뒤, 상근이를 불이 붙지 않은 곳으로 이동시키면 된다.

 

문제에서 어디로 갔을 때 탈출을 한다고 명시가 안 되어있어서 한참 찾았는데, 건물의 가장자리로 상근이가 이동하게 되면 그 다음 1초 뒤에 탈출이 가능하다.

 

---

 

코드

#include <iostream>
#include <queue>

using namespace std;

int dir[4][2] = { {1,0}, {-1,0}, {0,1}, {0,-1} };
char building[1001][1001];
int W, H;

struct location {
	int x, y;
	int time;
};

queue<location> human;
queue<location> fire;

void solve();
void input();
int move();

int main() {
	solve();

	return 0;
}

void solve() {
	int test_case;

	cin >> test_case;

	for (int t = 0; t < test_case; t++) {
		input();

		int res = move();

		while (!human.empty())
			human.pop();

		while (!fire.empty())
			fire.pop();

		if (res == -1)
			cout << "IMPOSSIBLE\n";
		else
			cout << res + 1 << "\n";
	}
}

void input() {
	cin >> W >> H;

	location temp;

	for (int i = 0; i < H; i++) {
		cin >> building[i];

		for (int j = 0; j < W; j++) {
			temp.x = j;
			temp.y = i;
			temp.time = 0;

			if (building[i][j] == '*') {
				fire.push(temp);
			}
			else if (building[i][j] == '@') {
				human.push(temp);
			}
		}
	}
}

int move() {
	while (true) {
		int size = fire.size();
		location cur, next;

		for (int i = 0; i < size; i++) {
			cur = fire.front();
			fire.pop();

			for (int j = 0; j < 4; j++) {
				next.x = cur.x + dir[j][0];
				next.y = cur.y + dir[j][1];

				if (0 <= next.x&&next.x < W && 0 <= next.y && next.y < H) {
					if (building[next.y][next.x] == '.' || building[next.y][next.x] == '@') {
						building[next.y][next.x] = '*';
						fire.push(next);
					}
				}
			}
		}

		size = human.size();

		for (int i = 0; i < size; i++) {
			cur = human.front();
			human.pop();

			if (cur.x == 0 || cur.y == 0 || cur.x == W - 1 || cur.y == H - 1)
				return cur.time;

			for (int j = 0; j < 4; j++) {
				next.x = cur.x + dir[j][0];
				next.y = cur.y + dir[j][1];
				next.time = cur.time + 1;

				if (0 <= next.x&&next.x < W && 0 <= next.y && next.y < H) {
					if (building[next.y][next.x] == '.') {
						building[next.y][next.x] = '*';
						human.push(next);
					}
				}
			}
		}

		if (human.size() == 0)
			return -1;
	}
}