C++) 백준 4179번 - 불!

https://www.acmicpc.net/problem/4179

4179번: 불!

BFS 알고리즘을 이용해야 하는 문제이다.

스트링을 2차원으로 선언해 입력을 받아왔다.

불의 확산 시간과 지훈이의 이동 시간을 표시할 두 배열을 선언했고

BFS를 위한 큐는 하나를 선언해 재활용 했다.

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

string board[1002]; //미로의 입력 받아올 board
int fire[1002][1002]; //불의 이동 시간 표시
int dist[1002][1002]; //지훈이의 이동 시간 표시
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
queue<pair<int,int> > q;
int jx,jy; //지훈의 초기 위치 저장

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int r,c; cin>>r>>c;
    for(int i=0;i<r;i++){
        cin>>board[i]; //미로 입력
    }
    for(int i=0;i<r;i++){ 
    //시간 나타낼 배열 초기화, -1인 경우 미방문
        for(int j=0;j<c;j++){
            fire[i][j]=-1;
            dist[i][j]=-1;
        }
    }
    
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            if(board[i][j]=='J'){
                jx=i; jy=j; //지훈 초기 위치 저장
                dist[i][j]=0; //시간=0
            }
            if(board[i][j]=='F'){
                q.push({i,j}); //불의 초기 위치 푸쉬
                fire[i][j]=0; //시간=0
            }
        }
    }

    while(!q.empty()){ //불의 확산시간 구하기
        auto cur=q.front(); q.pop();
        for(int i=0;i<4;i++){
            int nx=cur.first+dx[i];
            int ny=cur.second+dy[i];
            //예외처리
            if(nx>=r||nx<0||ny>=c||ny<0) continue; //접근 불가
            if(board[nx][ny]=='#'||fire[nx][ny]>=0) continue; //접근 불가이거나 이미 방문
            fire[nx][ny]=fire[cur.first][cur.second]+1;
            q.push({nx,ny});
        }
    }

    queue<pair<int,int> > q;
    q.push({jx,jy});
    while(!q.empty()){
        auto cur=q.front(); q.pop();
        for(int i=0;i<4;i++){
            int nx=cur.first+dx[i];
            int ny=cur.second+dy[i];
            if(nx>=r||nx<0||ny>=c||ny<0){ //접근 불가하단 것은 벽면에 도착했음을 의미
                cout<<dist[cur.first][cur.second]+1;
                return 0;
            }
            if(board[nx][ny]=='#'||dist[nx][ny]>=0) continue;
            //불에 대한 예외처리, 불의 확산 시간이 지훈의 이동시간보다 빠르거나 같은 경우
            if(fire[nx][ny]!=-1&&fire[nx][ny]<=dist[cur.first][cur.second]+1) continue;
            dist[nx][ny]=dist[cur.first][cur.second]+1;
            q.push({nx,ny});
        }
    }
    cout<<"IMPOSSIBLE"; //루프를 돌았음에도 도착에 실패한 경우
    return 0;
}