[BOJ] 불! 4179번 C++

 

 

문제

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

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

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

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

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

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

입력

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

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

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

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

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

출력

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

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

 

접근 방식

 

먼저 불이 도착했는지를 확인하고 지훈이가 갈 수 있는지를 확인 후 탈출해야한다

불이 도착했는지를 확인하기 위해

불의 갈 수 있는 최단 거리를 BFS 로 모두 구한 후

지훈이가 불의 최단 거리보다 적을 때 BFS를 돌 수 있게 해주면 된다

 

 

그림으로 그려보면 다음과 같다

지훈이의 좌표 (2,2)의 경우 도달 할 수 있는 최단거리가 2이기 때문에 불의 최단 거리 1보다 작으므로 갈 수 없다

마찬가지로 좌표(2,3)도 불의 최단 거리인 2보다 지훈이의 최단거리가 3으로 갈 수 없다

 

코드

#include<bits/stdc++.h>
using namespace std;

int R,C;
char mat[1002][1002];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int distJ[1002][1002];
int distF[1002][1002];

queue<pair<int,int>> J;
queue<pair<int,int>> F;


int main() {
    cin>>R>>C;

    for(int i=0; i<R; i++) {
        fill(distJ[i], distJ[i]+C, -1);
        fill(distF[i], distF[i]+C, -1);
    }
    for(int i=0; i<R; i++) {
        for(int j=0; j<C; j++) {
            cin>>mat[i][j];
            if(mat[i][j] == 'J') {
                J.push({i,j});
                distJ[i][j] = 0;
            }
            if(mat[i][j] == 'F') {
                F.push({i,j});
                distF[i][j] = 0;
            }
        }
    }

    while(!F.empty()) {
        int fx = F.front().first;
        int fy = F.front().second;
        F.pop();

        for(int r=0; r<4; r++) {
            int nfx = fx + dx[r];
            int nfy = fy + dy[r];

            if(nfx < 0 || nfy < 0 || nfx >= R || nfx >= C) continue;
            if(mat[nfx][nfy] == '#' | distF[nfx][nfy] != -1) continue;
            distF[nfx][nfy] = distF[fx][fy] + 1;
            F.push({nfx, nfy});
        }

    }

    while(!J.empty()) {
        int jx = J.front().first;
        int jy = J.front().second;
        J.pop();

        for(int r=0; r<4; r++) {
            int njx = jx + dx[r];
            int njy = jy + dy[r];

            if(njx < 0 || njy < 0 || njx >= R || njy >= C) {
                cout<<distJ[jx][jy]+1;
                return 0;
            }
            if(mat[njx][njy] == '#' || distJ[njx][njy] != -1) continue;
            if(distF[njx][njy] != -1 && distF[njx][njy] <= distJ[jx][jy] + 1) continue;
            distJ[njx][njy] = distJ[jx][jy] + 1;
            J.push({njx, njy});
        }

    }
    
    cout<<"IMPOSSIBLE";
}