4179: 불!

• toc {:toc}

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다)  이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

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

J는 입력에서 하나만 주어진다.

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

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

풀이

BFS는 결국 거리순으로 큐에 쌓인다. 큐에 빨리 들어가면 들어갈수록 가까운 거리임을 알 수 있다.

BFS의 궤는 같지만 세부적인 풀이는 다시 풀어봐야 할 것 같다.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
 
char board[1005][1005];
int dist_F[1005][1005];
int dist_J[1005][1005];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int R, C;
queue<pair<int, int>> fire, runner;
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> R >> C;
    
    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            dist_F[i][j] = -1;
            dist_J[i][j] = -1;
        }
    }
    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            cin >> board[i][j];
            if(board[i][j] == 'F'){
                fire.push({i, j});
                dist_F[i][j] = 0;
            }
            if(board[i][j] == 'J'){
                runner.push({i, j});
                dist_J[i][j] = 0;
            }
        }
    }
    while(!fire.empty()){               // 불에 대한 BFS
        auto cur = fire.front(); fire.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(board[nx][ny] == '#' || dist_F[nx][ny] >= 0) continue;
            dist_F[nx][ny] = dist_F[cur.X][cur.Y] + 1;
            fire.push({nx, ny});
        }
    }
    while(!runner.empty()){             // 지훈에 대한 BFS
        auto cur = runner.front(); runner.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 << dist_J[cur.X][cur.Y]+1;
                return 0;
            }
            if(dist_J[nx][ny] >= 0 || board[nx][ny] == '#') continue;
            if(dist_F[nx][ny] != -1 && dist_F[nx][ny] <= dist_J[cur.X][cur.Y]+1) continue;  // 중요!!!
            dist_J[nx][ny] = dist_J[cur.X][cur.Y] + 1;      // 불로 인해 지훈이가 갈 수 없는 경우 제외
            runner.push({nx, ny});                          // 불이 안지나가도 -1이 기본값이기에 -1일 때는 지나갈 수 있도록 처리
        }
    }
    cout << "IMPOSSIBLE";
 
    return 0;
}