BOJ 4179 ) 불! (C++)

4179번: 불!

 BFS로 풀리는 문젠데 예외 처리 하는 부분에서 미처 고려하지 못한 부분이 있어 좀 헤맸다. 

1. 불의 이동경로에 대한 큐와 지훈이의 이동 경로에 대한 큐를 각각 만들어주고 입력을 받으면서 시작점들을 각 큐에 입력해준다. 그리고 지훈이의 이동 시간을 체크할 배열(dist)과 불의 이동 시간을 체크할 배열(burn)에 이동 가능한 좌표를 -1로 체크해준다. (따로 체크하지 않은 좌표는 0으로 초기화 되어 있으므로 추후 방문여부 체크 시 해당 좌표가 0 이상의 값을 가지는 경우 방문하지 않게 할 수 있다.) 지훈이는 불의 시작점을 방문 할 수 없지만 불은 지훈이의 시작점도 방문할 수 있도록 해야한다. 

2. 불의 이동 시간을 체크한다. 일반적인 BFS로 가능하다. 

3. 지훈이의 이동 시간을 체크한다. 다음에 방문할 좌표가 미로 밖이면 탈출에 성공한 것이므로 지금까지의 이동경로 + 1 을 출력하고 종료한다. 좌표가 미로 내부라면 방문할 수 있는 칸인지(벽이거나 이미 불타고 있는 칸이 아닌지) 체크한다.

if(dist[nx][ny] >=0 || burn[nx][ny]!=-1 && burn[nx][ny] <= dist[cur.x][cur.y]+1 ) continue;

  burn[nx][ny] <= dist[cur.x][cur.y]+1 는 다음 칸에 아직 불이 오지 않았는지를 체크한다. 하지만 burn[nx][ny] 이 -1인 경우를 고려해주지 않으면 지나갈 수 있는 경로임에도 불구하고 지나가지 않게 되어 문제가 발생한다. 이 부분을 놓쳐서 시간을 많이 허비했다. 

#include <bits/stdc++.h>
#define pii pair<int,int>
#define x first 
#define y second
using namespace std;

int R, C;
char arr[1006][1010];
int dist[1002][1002];
int burn[1002][1002];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

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

  cin>>R>>C;
  string s;
  queue<pii> jihoon;
  queue<pii> fire;

  for(int i=0; i<R; i++){
    cin>>s;
    for(int j=0; j<C; j++){
      arr[i][j] = s[j];
      if(arr[i][j]=='.'){
        dist[i][j]=-1;
        burn[i][j]=-1;
      }if(arr[i][j]=='J'){
        burn[i][j]=-1;
        jihoon.push({i,j});
      }if(arr[i][j]=='F'){
        fire.push({i,j});
      }
    }
  }

  while(!fire.empty()){
    pii cur = fire.front();
    fire.pop();

    for(int i=0;i<4; i++){    
      int nx = cur.x+dx[i];
      int ny = cur.y+dy[i];
      if(nx<0||ny<0||nx>=R||ny>=C) continue;
      if(burn[nx][ny] >=0) continue;
      burn[nx][ny] = burn[cur.x][cur.y] + 1;
      fire.push({nx,ny});
    }
  }
  
  while(!jihoon.empty()){
    pii cur = jihoon.front();
    jihoon.pop();
    
    for(int i=0; i<4; i++){
      int nx = cur.x+dx[i];
      int ny = cur.y+dy[i];
      if(nx<0||ny<0||nx>=R||ny>=C){ 
        cout<<dist[cur.x][cur.y]+1;
        return 0;
      }
      if(dist[nx][ny] >=0 || burn[nx][ny]!=-1 && burn[nx][ny] <= dist[cur.x][cur.y]+1 ) continue;
      dist[nx][ny] = dist[cur.x][cur.y] + 1;
      jihoon.push({nx,ny});
    }
  }
  cout<<"IMPOSSIBLE";
  return 0;
}