❓문제 설명

문제 : 백준 4179번 불!
난이도 : 골드 4

문제 요약

• 지훈이를 미로에서 탈출하도록 도와주자!
• 초기 미로에는 지훈이의 위치와 불이 붙은 위치를 알려줍니다.
• 이때, 매 분마다 지훈이는 수평또는 수직으로 한칸씩 이동하고 불은 각 지점에서 네 방향으로 확산됩니다.
• 지훈이는 미로의 가장자리에 접한 공간에서 탈출 가능합니다.
• 지훈이와 불은 벽이 있는 공간은 통과하지 못합니다.
• 지훈이가 탈출할 수 있는 가장 빠른 탈출시간을 출력하고 탈출 못하면 IMPOSSIBLE을 출력합니다.

• # : 벽
• . : 지나갈 수 있는 공간
• J : 지훈이의 미로에서의 초기위치
• F : 불이 난 공간

🎯문제 해결 방법

이 문제는 BFS 알고리즘을 사용해서 풀면 쉽게 풀립니다.

불이 전파되는 시간을 먼저 구하고 지훈이가 탈출하는 시간을 구할 때 해당 거리까지 이동 시간보다 불이 전파되는 시간 빠르면 이동 가능한 점을 이용합니다.

for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		if (board[i][j] == 'F') {
			Q1.push({ i,j });
            dist1[i][j] = 0;
		}
		if (board[i][j] == 'J') {
			Q2.push({ i,j });
			dist2[i][j] = 0;
		}
	}
}

Q1에는 불이 있는 위치들을 넣습니다.
Q2에는 지훈이의 위치를 넣습니다.

while (!Q1.empty()) {
		auto cur = Q1.front(); Q1.pop();

		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (dist1[nx][ny] >= 0 || board[nx][ny] == '#') continue;
			dist1[nx][ny] = dist1[cur.X][cur.Y] + 1;
			Q1.push({ nx,ny });

		}
	}

위에서 말한대로 불의 전파 시간을 구합니다.

while (!Q2.empty()) {
		auto cur = Q2.front(); Q2.pop();

		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
				cout << dist2[cur.X][cur.Y] + 1;
				return 0;
			}
			if (dist2[nx][ny] >= 0 || board[nx][ny] == '#') continue;
			if (dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.X][cur.Y] + 1) continue;

			dist2[nx][ny] = dist2[cur.X][cur.Y] + 1;
			Q2.push({ nx,ny });

		
 		}
	}

다음으로 지훈이의 이동거리를 구하고 미로의 가장자리를 넘어가는 순간이 오면 가장 빠른 탈출 시간을 출력하고 프로그램을 종료합니다.

💻전체 코드

#include<iostream>
#include<string>
#include<queue>
#include<utility>

#define X first
#define Y second

using namespace std;


string board[1001];

int dist1[1001][1001]; //불의 전파 시간
int dist2[1001][1001]; // 탈출 속도

int n, m;

int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

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

	queue<pair<int, int>> Q1; //불
	queue<pair<int, int>> Q2; //탈출

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> board[i];
	}

	for (int i = 0; i < n; i++) {
		fill(dist1[i], dist1[i] + m, -1);
		fill(dist2[i], dist2[i] + m, -1);
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (board[i][j] == 'F') {
				Q1.push({ i,j });
				dist1[i][j] = 0;
			}
			if (board[i][j] == 'J') {
				Q2.push({ i,j });
				dist2[i][j] = 0;
			}
		}
	}

	while (!Q1.empty()) {
		auto cur = Q1.front(); Q1.pop();

		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (dist1[nx][ny] >= 0 || board[nx][ny] == '#') continue;
			dist1[nx][ny] = dist1[cur.X][cur.Y] + 1;
			Q1.push({ nx,ny });

		}
	}


	while (!Q2.empty()) {
		auto cur = Q2.front(); Q2.pop();

		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
				cout << dist2[cur.X][cur.Y] + 1;
				return 0;
			}
			if (dist2[nx][ny] >= 0 || board[nx][ny] == '#') continue;
			if (dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.X][cur.Y] + 1) continue;

			dist2[nx][ny] = dist2[cur.X][cur.Y] + 1;
			Q2.push({ nx,ny });

		
 		}
	}
	cout << "IMPOSSIBLE";

}