BOJ - 4179 - 불!

ggh·2022년 8월 22일

BFS boj cpp ps

백준

목록 보기

62/112

BOJ - 4179 - 불!

문제

4179번: 불!

문제

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

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

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

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

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

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

입력

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

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

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

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

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

출력

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

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

구현

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// map
int n, m;
int map[1004][1004];
int Jvisited[1004][1004];
int Fvisited[1004][1004];
// joy
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};

// x, y
int x, y, jx, jy, fx, fy;
vector<pair<int, int>> v;
// q 
queue<pair<int, int>> fq;
queue<pair<int, int>> jq;

int main()
{
    cin >> n >> m;
    // map 이진화 
    for(int i=0; i < n; i++)
        for(int j=0; j < m; j++)
        {
            char tmp;
            cin >> tmp;
            if(tmp == '#')
                map[i][j] = 1;
            else if(tmp == '.')
                map[i][j] = 0;
            else if(tmp == 'J')
            {
                jy = i;
                jx = j;
            }
            else
            {
                fq.push({i, j});
                Fvisited[i][j] = 1;
            }
        }
    
    jq.push({jy, jx});
    Jvisited[jy][jx] = 1;

    // 최단거리 
    while (fq.size())
    {
        fx = fq.front().second;
        fy = fq.front().first;
        fq.pop();

        for(int i=0; i < 4; i++)
        {
            int ny = fy + dy[i];
            int nx = fx + dx[i];
            
            if(ny < 0 || nx < 0|| ny >= n || nx >= m)
                continue;
            // 벽일 경우, 이미 방문 했을 경우 
            if(map[ny][nx] || Fvisited[ny][nx])
                continue;
            Fvisited[ny][nx] = Fvisited[fy][fx] + 1;
            fq.push({ny, nx});
        }
    }
    while(jq.size())
    {
        y = jq.front().first;
        x = jq.front().second;
        jq.pop();

        for(int i=0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            
            if(ny < 0 || nx < 0|| ny >= n || nx >= m)
                continue;
            // 벽일 경우, 이미 방문 했을 경우 
            if(map[ny][nx] || Jvisited[ny][nx])
                continue;
            Jvisited[ny][nx] = Jvisited[y][x] + 1;
            jq.push({ny, nx});
        }
    }
    // 불을 피해가는 최단거리 값
    for(int i=0; i < n; i++)
        for(int j=0; j < m; j++)
           if(Jvisited[i][j] >= Fvisited[i][j] && Fvisited[i][j])
                Jvisited[i][j] = 0;    

    int min = 9999;
    for(int i=0; i < n; i++)
    {
        if(i == 0 || i == n-1)
        {
            for(int j=0; j < m; j++)
                if(min > Jvisited[i][j] && Jvisited[i][j])
                    min = Jvisited[i][j];
        }
        else
        {
            if(min > Jvisited[i][0] && Jvisited[i][0])
                min = Jvisited[i][0];
            else if(min > Jvisited[i][m-1] && Jvisited[i][m-1])
                min = Jvisited[i][m-1];
        }
    }
   // map 출력
    // cout << "---------------" << endl;
    // for(int i=0; i < n; i++)
    // {
    //     for(int j=0; j < m; j++)
    //     {
    //        cout << Jvisited[i][j] << " ";
    //     }   
    //     cout << endl;
    // }
    // 출구가 존재하면
    if(min != 9999)
        cout << min << endl;
    else
        cout << "IMPOSSIBLE " << endl;

    return 0;
}