백준 4179번 불!

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

 

아이디어:

1. 불에 대한 BFS와 지훈이에 대한 BFS를 따로 진행

2. 'F'를 모두 찾고 거리(= 시간)를 기록하는 BFS 수행

3. J를 찾고 'F' 도착시간보다 늦거나 같이 도착하는 경우, 이미 불이 지나간 경우를 검사하면서 거리(= 시간)를 기록하는 BFS 수행

4. J의 BFS 도중 범위를 벗어나면 탈출한 것으로 거리(= 시간)를 출력하며 종료

 

초기 'J'의 위치가 i = 0, i = n - 1, j = 0, j = m - 1인 경우일 때 바로 return하는 풀이

 

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

char board[1001][1001];
int vis[1001][1001];
int fire[1001][1001];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	for (int i = 0; i < 1001; i++) {
		fill(board[i], board[i] + 1001, '#');
	}

	int n, m;
	string tmp;
	queue<pair<int, int>> Q;
	cin >> n >> m;

	for (int i = 0;i < n;i++) {
		cin >> tmp;
		int j = 0;
		for (auto x : tmp) {
			board[i][j] = x;
			j++;
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (board[i][j] == 'F') {
				fire[i][j] = 1;
				Q.push({ i, j });
			}
		}
	}

	while (!Q.empty()) {
		pair<int, int> cur = Q.front();
		Q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (fire[nx][ny] != 0 || board[nx][ny] != '.') continue;
			fire[nx][ny] = fire[cur.first][cur.second] + 1;
			Q.push({ nx, ny });
		}
	}

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (board[i][j] == 'J') {
				if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
					cout << 1;
					return 0;
				}
				vis[i][j] = 1;
				Q.push({ i, j });
			}
		}
	}

	while (!Q.empty()) {
		pair<int, int> cur = Q.front();
		Q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
				cout << vis[cur.first][cur.second];
				return 0;
			};
			if (vis[nx][ny] != 0 || board[nx][ny] != '.') continue;
			if (vis[cur.first][cur.second] + 1 >= fire[nx][ny] && fire[nx][ny] > 0) continue;
			vis[nx][ny] = vis[cur.first][cur.second] + 1;
			
			Q.push({ nx, ny });
		}

	}

	cout << "IMPOSSIBLE";

	return 0;

}