[BOJ] 5427 : fire - travelbeeee

문제 : https://www.acmicpc.net/problem/5427

---

[알고리즘풀이]

BFS를 이용하는 전형적인 문제다.

사람은 불이 없더라도, 이제 불이 옮겨붙으려는 칸으로도 이동할 수 없다.

따라서, 먼저 불을 다 이동시키고, 남는 자리에 한해서 사람이 이동하면 된다.

사람이 밖으로 탈출하면 성공한 것이므로 check 함수를 통해

사람이 다음에 이동할 곳 중 밖으로 나가는 곳이 있으면 이동 횟수를 출력하고 종료해주면 된다.

#include<iostream>
#include<string>
#include<queue>
#include<vector>

using namespace std;

char map[1000][1000] = {};
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
int t, r, c;

bool check(int x, int y) {
	if (0 <= x && x < r && 0 <= y && y < c)
		return true;
	return false;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> t;
	while (t--) {
		cin >> c >> r;
		for (int i = 0; i < r; i++)
			cin >> map[i];

		bool ch = false; // IMPOSSIBLE인지 아닌지 체크
		bool visited[1000][1000] = {}; // BFS 경로
		queue<pair<int, int>> fire;
		queue<pair<pair<int, int>, int>> q;
		for(int i = 0; i < r; i++)
			for (int j = 0; j < c; j++) {
				if (map[i][j] == '*')
					fire.push(make_pair(i, j));
				if (map[i][j] == '@'){
					q.push(make_pair(make_pair(i, j), 0));
					visited[i][j] = true;
				}
			}

		while (!q.empty()) {
			// 불부터 옮기자.
			int sx, sy;
			int end = fire.size();
			for (int i = 0; i < end; i++) {
				pair<int, int> fire_s = fire.front();
				fire.pop();
				for (int j = 0; j < 4; j++) {
					sx = dx[j] + fire_s.first;
					sy = dy[j] + fire_s.second;
					if (check(sx, sy) && map[sx][sy] == '.') {
						map[sx][sy] = '*';
						fire.push(make_pair(sx, sy));
					}
				}
			}
			// 사람을 이동하자.
			end = q.size();
			for (int i = 0; i < end; i++) {
				pair<pair<int, int>, int> s = q.front();
				q.pop();		
				for (int j = 0; j < 4; j++) {
					sx = dx[j] + s.first.first;
					sy = dy[j] + s.first.second;
					if (!check(sx, sy)) {
						cout << s.second + 1 << '\n';
						ch = true;
						break;
					}
					if (map[sx][sy] == '.' && visited[sx][sy] == false) {
						q.push(make_pair(make_pair(sx, sy), s.second + 1));
						visited[sx][sy] = true;
					}
				}
				if (ch) break;
			}
			if (ch) break;
		}
		if (ch) continue;
		cout << "IMPOSSIBLE\n";
	}
}

---