[BaekJoon] 4179번 : 불!

• 이 글은 c++로 풀이를 작성하였습니다.

문제

 

예시

 

풀이

• BFS 활용하는 문제로 불에 시작점에서 BFS를 돌린 후 지훈이를 BFS를 진행하여 불이 먼저 확산된 경우 진행할 수 없도록 합니다.
• 주의해야할 점은 2가지로 불이 여러 개 존재할 수 있다는 점과, 불이 없을 수도 있다는 점입니다.
• 즉, 불이 여러 개 존재는 BFS를 똑같이 해도 괜찮지만, 불이 없는 경우에는 불이 이동한 거리 배열은 초기화인 상태 그래도 있습니다.

#include<iostream>
#include<queue>
#include<utility>
#include<string>
using namespace std;

int n,m;
int arr[1000][1000];
int fdist[1000][1000];
int jdist[1000][1000];
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};

bool inside(int y,int x){
    return 0<=y && y<n && 0<=x && x<m;
}

bool isboarder(int y,int x){
    return y == 0 || x == 0 || y == n-1 || x == m-1;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    queue<pair<int,int>> fq;
    queue<pair<int,int>> jq;
    
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        for(int j=0;j<m;j++){
            if(s[j] == '#'){
                arr[i][j] = -1;
            }else if(s[j] == '.'){
                arr[i][j] = 0;
            }else if(s[j] == 'J'){
                arr[i][j] = 1;
                jq.push({i,j});
                jdist[i][j] = 1;
            }else{
                arr[i][j] = 2;
                fq.push({i,j});
                fdist[i][j] = 1;
            }
        }
    }
    
    while(!fq.empty()){
        int y = fq.front().first;
        int x = fq.front().second;
        fq.pop();
        
        for(int i=0;i<4;i++){
            int dy = y + dir[i][0];
            int dx = x + dir[i][1];
            
            if(inside(dy,dx) && arr[dy][dx]!=-1 && !fdist[dy][dx]){
                fq.push({dy,dx});
                fdist[dy][dx] = fdist[y][x] + 1;
            }
        }
    }
    
    while(!jq.empty()){
        int y = jq.front().first;
        int x = jq.front().second;
        jq.pop();
        
        for(int i=0;i<4;i++){
            int dy = y + dir[i][0];
            int dx = x + dir[i][1];
            
            if(!inside(dy, dx)){
                cout<<jdist[y][x];
                return 0;
            }
            
            if(arr[dy][dx]!=-1 && jdist[dy][dx] == 0){
                if(fdist[dy][dx] == 0 || (jdist[y][x] + 1 < fdist[dy][dx])){
                    jq.push({dy,dx});
                    jdist[dy][dx] = jdist[y][x] + 1;
                }
            }
        }
    }
    
    cout<<"IMPOSSIBLE";
    
}

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요,.