[c++] 백준 4179, 불!

백준 4179

🌲 문제 요약

미로 속 지훈이와 불이 매 분마다 한 칸씩, 수평 또는 수직으로 이동한다고 할 때, 지훈이가 불을 피해 미로를 탈출할 수 있는 가장 빠른 탈출 시간을 구하는 문제.

🌲 문제 풀이

불의 이동 경로와 지훈이의 이동 경로를 따로 나누어 해결한다.
BFS를 이용하여 불의 방문 정보가 담긴 배열 visited_fire를 먼저 완성한 뒤, 마찬가지로 BFS를 이용하여 지훈이의 방문 정보가 담긴 배열 visited를 완성한다.
이때, 지훈이는 visited[y][x] + 1 < visited_fire[ny][nx]를 만족할 때, 다음 구역으로의 이동이 가능하며, 만약 지훈이가 미로의 가장자리에 도달하였다면, ret에 visited[y][x]의 값을 저장한다.

🌲 주의

처음 visited_fire의 값을 초기화할 때, 0이 아닌 INF로 초기화해야 함에 주의한다. 만약 0으로 초기화하게 되면, 지훈이는 불이 없는 구역임에도 이동할 수 없는 불상사가 발생하게 된다.

🌲 코드

#include <bits/stdc++.h>

using namespace std;
#define INF 987654321
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int r, c, y, x, ret, visited[1005][1005], visited_fire[1005][1005];
char a[1005][1005];
queue<pair<int, int>> q, q_fire;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> r >> c;
	fill(&visited_fire[0][0], &visited_fire[0][0] + 1005 * 1005, INF);
	// 0으로 초기화가 아닌 INF로 초기화
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> a[i][j];
			if (a[i][j] == 'J') {
				visited[i][j] = 1;
				q.push({i, j});
			}
			else if (a[i][j] == 'F') {
				visited_fire[i][j] = 1;
				q_fire.push({i, j});
			}
		}
	}
	
	while (q_fire.size()) {
		tie(y, x) = q_fire.front(); q_fire.pop();
		for (int i = 0; i < 4; i++ ) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue;
			if (visited_fire[ny][nx] != INF || a[ny][nx] == '#') continue;
			visited_fire[ny][nx] = visited_fire[y][x] + 1;
			q_fire.push({ny, nx});
		}
	}
	
	while (q.size()) {
		tie(y, x) = q.front(); q.pop();
		if (y == 0 || y == r - 1 || x == 0 || x == c - 1) {
			ret = visited[y][x];
			break;
		}
		for (int i = 0; i < 4; i++ ) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue;
			if (visited[ny][nx] || a[ny][nx] == '#') continue;
			if (visited[y][x] + 1 < visited_fire[ny][nx]) { 
				// 0으로 초기화하면 불이 없는 구역으로 이동 불가 
				visited[ny][nx] = visited[y][x] + 1;
				q.push({ny, nx});
			}
		}
	}
	if (ret) cout << ret << '\n';
	else cout << "IMPOSSIBLE \n";
	
	return 0;
}