문제 설명

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

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

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

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

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

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

입력

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

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

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

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

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

출력

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

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

문제 풀이

간단히 설명하면 불의 bfs, 사람의 bfs 두번 돌리면 되는 문제이다. 하지만 실수할 여지가 많아 시간을 상당히 많이 잡아먹었다.
첫 실수는 예제만 보고 불이 두 개 이상 있는 경우를 가정하지 못한 것이다. 불이 두 개 이상인 경우 fire 배열에 더 작은 값을 넣어줘야 하지만 그 부분의 예외처리를 하지 못했었다.
두 번째 실수는 불이 닿지 않는 경우를 예외처리 하지 않아 불이 닿지 않았을 때의 값인 0이 지훈이가 그 자리에 도달하는 시간보다 무조건 작으므로 제대로 된 정답이 출력되지 않는 것이다.
이 두 부분을 처리하고 나니 무사히 정답을 도출할 수 있었다. bfs는 기본 식이 간단하기 때문인지 응용 문제가 많아 문제 풀이 경험이 중요한 것 같다.

코드

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

char table[1005][1005];
int m_visited[1005][1005]; //지훈이의 visited 배열
int fire_visited[1005][1005]; //불의 visited 배열
int fire[1005][1005]; //불이 그 자리에 몇초에 도달하는지를 담은 배열
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int mini=100000000;
int n, m;

bool oob(int x, int y) {
    if(x>=0 && x<n && y>=0 && y<m) return true;
    else return false;
}

struct mov {
    int x; int y; int time;
}; //좌표와 좌표에 도달한 시간을 담는 구조체

void fire_bfs(int x, int y) {
    queue<mov> q; q.push({x,y,0});
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            fire_visited[i][j]=0;
        }
    }
    fire_visited[x][y]=1; fire[x][y]=0;
    while(!q.empty()) {
        mov mo=q.front(); q.pop();
        for(int i=0; i<4; i++) {
            int xx=mo.x+dx[i];
            int yy=mo.y+dy[i];
            int tt=mo.time+1;
            if(oob(xx,yy) && table[xx][yy]!='#' && !fire_visited[xx][yy]) {
                fire_visited[xx][yy]=1; q.push({xx,yy,tt});
                if(fire[xx][yy]!=0) fire[xx][yy]=min(fire[xx][yy],tt);
                else fire[xx][yy]=tt;
            }
        }
    }
//불을 bfs를 돌려 각 좌표에 불이 도달하는 최소 시간을 담은 fire 배열을 얻는다
}

void m_bfs(int x, int y) {
    queue<mov> q; q.push({x,y,0});
    m_visited[x][y]=1;
    if(x==0 || x==n-1 || y==0 || y==m-1) mini=0;
    while(!q.empty()) {
        mov mo=q.front(); q.pop();
        for(int i=0; i<4; i++) {
            int xx=mo.x+dx[i];
            int yy=mo.y+dy[i];
            int tt=mo.time+1;
            if(oob(xx,yy) && table[xx][yy]=='.' && !m_visited[xx][yy]) {
                if(fire[xx][yy]==0 || (fire[xx][yy]!=0 && tt<fire[xx][yy])) {
                    m_visited[xx][yy]=1;
                    if(xx==0 || xx==n-1 || yy==0 || yy==m-1) {
                        if(tt<mini) mini=tt;
                    }
                    else q.push({xx, yy, tt});
                    }
            }
        }
    }
}//fire 배열에 담긴 불이 도달하는 시간보다 더 빨리 지훈이가 도달한다면 bfs의
// queue에 넣어준다.

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            cin >> table[i][j];
        }
    }
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            if(table[i][j]=='F') fire_bfs(i,j);
        }
    }//불들을 먼저 bfs를 돌려준 후 지훈이의 bfs 시작
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            if(table[i][j]=='J') m_bfs(i,j);
        }
    }
    if(mini==100000000) cout << "IMPOSSIBLE";
    else cout << mini+1;
}