4179번: 불! (BOJ C/C++)

4179번: 불!

사용 언어: C++

 

문제

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

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

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

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

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

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

입력

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

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

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

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

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

출력

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

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

 

풀이

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

string board[1002];
int dist1[1002][1002]; // 불의 전파 시간
int dist2[1002][1002]; // 지훈이의 이동 시간
int n, m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

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

    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        //fill -1로 dist1, dist2 초기화
        fill(dist1[i], dist1[i]+m, -1);
        fill(dist2[i], dist2[i]+m, -1);    
    }
    for(int i = 0; i < n; i++)
        cin >> board[i];  
    queue<pair<int,int> > Q1;
    queue<pair<int,int> > Q2;
    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;
            }
        }
    }

    // 불에 대한 BFS
    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});
        }
    }

    // 지훈이에 대한 BFS
    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";
}