[ 백준 4179 - 불 ]

[ 문제 풀이 ]

BFS에서 시작점이 2개이고 시작저믜 종류가 서로 다를 경우에 해당하는 문제이다. 대표적인 유형이다. 불에 대한 BFS를 먼저 돌리고 해당 정보를 기준으로 지훈이에 대한 BFS를 돌리면 된다.

[ 실수한 부분 ]

4 4
###F
#J.#
#..#
##.#

과 같이 불이 벽에 막혀 있을경우 제대로 동작하지 않는다. 해당 칸에 대해서 방문하지 않은 표시를 -1로 표현해 놓았는데

다음과 같은 경우에서 -1은(방문하지 않음) 항상 0(0일차에 방문함)보다 작기때문에 실제로는 -1로 된 칸은 방문해야 하지만 방문하지 못하고 pass하게 된다. 메모리 여유가 있다면 방문여부에 대한 배열과 언제 방문 했는지에 대한 배열을 따로 관리하는 것이 좋을것 같다

[ 소스코드 ]

[ 소스코드 원본 ]

#include <iostream>
#include <queue>

using namespace std;

string board[1002];
int vis_fire[1002][1002];
int vis_jh[1002][1002];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int row;
int col;
queue<pair<int,int> > QF;
queue<pair<int,int> > QJH;

void init(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}

void get_input(){

    cin >> row >> col;

    for(int i = 0 ; i < row ; i++){
        for(int j = 0 ; j < col ; j++){
            vis_fire[i][j] = -1;
            vis_jh[i][j] = -1;
        }
    }

    for(int i = 0 ; i < row ; i++){
        cin >> board[i];
    }
}

void fire_bfs(){
    for(int i = 0; i < row ; i++){
        for(int j = 0 ; j < col; j++){
            if(board[i][j] == 'F'){
                vis_fire[i][j] = 0;
                QF.push(make_pair(i,j));
            }
        }
    }

    while(!QF.empty()){
        pair<int,int> cur = QF.front(); QF.pop();
        for(int dir = 0 ; dir < 4; dir++){

            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];

            if(nx < 0 || nx >= row || ny < 0 || ny >= col) continue;
            if(vis_fire[nx][ny] != -1 || board[nx][ny] == '#') continue;

            vis_fire[nx][ny] = vis_fire[cur.first][cur.second] + 1;
            QF.push(make_pair(nx,ny));
        }
    }
}

int jh_bfs(){

    for(int i = 0; i < row ; i++){
        for(int j = 0 ; j < col; j++){
            if(board[i][j] == 'J'){
                vis_jh[i][j] = 0;
                QJH.push(make_pair(i,j));
            }
        }
    }

    while(!QJH.empty()){

        pair<int,int> cur = QJH.front(); QJH.pop();
        for(int dir = 0 ; dir < 4; dir++){

            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];

            if(nx < 0 || nx >= row || ny < 0 || ny >= col) { 
                cout << vis_jh[cur.first][cur.second] + 1 << "\n";
                return 1;
            }

            if(vis_jh[nx][ny] != -1 || board[nx][ny] == '#') continue;

            if((vis_fire[nx][ny] != -1 && vis_fire[nx][ny] <= vis_jh[cur.first][cur.second] + 1)) continue;

            vis_jh[nx][ny] = vis_jh[cur.first][cur.second] + 1;
            QJH.push(make_pair(nx,ny));
        }
    }
    return 0;
}

int main(){
    init();
    get_input();
    fire_bfs();
    if(jh_bfs()) return 0;
    cout << "IMPOSSIBLE\n" ;
    return 0;
}