링크
https://www.acmicpc.net/problem/4179
문제
지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!
미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.
지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.
불은 각 지점에서 네 방향으로 확산된다.
지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.
지훈이와 불은 벽이 있는 공간은 통과하지 못한다.
입력
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
다음 입력으로 R줄동안 각각의 미로 행이 주어진다.
각각의 문자들은 다음을 뜻한다.
#: 벽
.: 지나갈 수 있는 공간
J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
F: 불이 난 공간
J는 입력에서 하나만 주어진다.
출력
지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.
지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.
풀이
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#define X first
#define Y second
using namespace std;
int r, c;
string board[1001];
int dist1[1001][1001]; //불의 전파 시간
int dist2[1001][1001]; //J의 이동시간
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
int main(void) {
//먼저 불이 지나가는 bfs 구하고 J가 가는 길 bfs를 구한다.
ios::sync_with_stdio(0);
cin.tie(0);
cin >> r >> c;
for (int i = 0; i < r; i++) { //모든 dist -1로 초기화
fill(dist1[i], dist1[i] + c, -1);
fill(dist2[i], dist2[i] + c, -1);
}
for (int i = 0; i < r; i++) {
cin >> board[i];
}
queue <pair<int, int>> q1;
queue <pair<int, int>> q2;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; 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;
}
}
}
//불에 대한 bfs
while (!q1.empty()) {
pair <int, int > 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 >= r || ny < 0 || ny >= c) continue;
if (dist1[nx][ny] >= 0 || board[nx][ny] == '#') continue;
dist1[nx][ny] = dist1[cur.X][cur.Y] + 1;
q1.push({ nx, ny });
}
}
//J에 대한 bfs
while (!q2.empty()) {
pair <int, int> 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 >= r || ny <0 || ny >= c) { // 범위를 넘긴다는 것은 곧 탈출에 성공했다는 의미. 큐에 반드시 거리순으로 들어가므로 최초에 탈출한 시간을 입력하면 됨.
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;
//해당 칸에 J가 가는 최소 시간이 불길이 닿는 시간보다 같거나 크면 해당 칸에 갈 수 없다. 불의 전파 시간을 조건에 추가.
dist2[nx][ny] = dist2[cur.X][cur.Y] + 1;
q2.push({ nx, ny });
}
}
cout << "IMPOSSIBLE"; // 여기에 도달했다는 것은 탈출에 실패를 의미.
}설명
👨🏻🏫 불에 대한 bfs, 지훈에 대한 bfs를 따로 돌려서 해결 가능하다. 먼저 불에 대한 bfs를 돌려서 미리 각 칸에 불이 전파되는 시간을 모두 구한다. 그 다음에 지훈이 bfs를 구하는데 해당 칸에 J가 가는 최소 시간이 불길이 닿는 시간보다 같거나 크면 해당 칸에 갈 수 없다. 불의 전파 시간을 조건에 추가해야한다.
⭐ 지금까지는 bfs에서는 목적지가 정해져있거나 더이상 갈 곳이 없을때가지 계속 돌리는 상황이었던 반면 이번에는 외곽으로 탈출해야한다. 범위를 넘긴다는 것은 곧 탈출에 성공했다는 의미함. 큐에 반드시 거리순으로 들어가므로 최초에 탈출한 시간을 입력하고 리턴하면 됨.
📌 지훈이는 불의 영향을 받지만 불의 전파는 지훈이의 영향을 받지 않아서 불만 먼저 전파를 시키는게 가능했다. 그런데 만약 B가 서로 영향을 주는 상황이라면 어느 한쪽을 먼저 끝까지 전파 시키는게 불가능 하다. 시간 순으로 A와 B를 동시에 진행시켜야한다.
