[BOJ] 4179 : Fire! - travelbeeee

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

---

BOJ 5427번 문제와 매우 유사하다.

BFS 탐색을 불을 먼저 다 이동하고, 사람을 이동하면서 진행하면 된다.

#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  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 >> r >> c;
	for (int i = 0; i < r; i++)
		cin >> map[i];

	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] == 'F')
				fire.push(make_pair(i, j));
			if (map[i][j] == 'J') {
				q.push(make_pair(make_pair(i, j), 0));
				visited[i][j] = true;
				map[i][j] = '.';
			}
		}

	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] = 'F';
					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';
					return 0;
				}
				if (map[sx][sy] == '.' && visited[sx][sy] == false) {
					q.push(make_pair(make_pair(sx, sy), s.second + 1));
					visited[sx][sy] = true;
				}
			}
		}

	}
	cout << "IMPOSSIBLE\n";
	return 0;
}

---