문제

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

입력예제

4 4
####
#JF#
#..#
#..#

풀이

불은 지훈이가 한 번 이동할 때마다 상하좌우로 한칸씩 늘어난다.
지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. -> 범위 밖으로 나가면 탈출한 것!

지훈이가 한번 움직일떄마다 불이 상하좌우로 퍼져야한다.

풀이 1 - 틀린 풀이

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

char board[1001][1001];
int dist[1001][1001]={-1};
int dist2[1001][1001]={-1};

int R, C;
queue<pair<int, int>> Q;
queue<pair<int, int>> Q2;

void fire(){
    while(!Q2.empty()){
        auto cur = Q2.front();
        Q2.pop();
        
        
        //상하좌우 확인하기
        for(int dir=0; dir<4; dir++){
            int nx = cur.first+dx[dir];
            int ny = cur.second+dy[dir];
            
            //범위 확인하기
            if(nx<0||ny<0||nx>=R||ny>=C) continue;
            //방문했거나 벽이면 pass
            if(dist2[nx][ny]>=0 || board[nx][ny]=='#') continue;
            
            dist2[nx][ny] = dist2[cur.X][cur.Y]+1;
            Q2.push({nx, ny});
            
        }
        
    }
}

void bfs(){
    while(!Q.empty()){
        auto cur = Q.front();
        Q.pop();
        
        
        //상하좌우 확인하기
        for(int dir=0; dir<4; dir++){
            int nx = cur.first+dx[dir];
            int ny = cur.second+dy[dir];
            
            //범위 확인하기-> 범위 밖으로 나가면 탈출 성공
            if(nx<0||ny<0||nx>=R||ny>=C) {
                cout << dist[cur.X][cur.Y]+1; return;}
            //방문했거나 벽이거나 불이 나 있으면 pass
            if(dist[nx][ny]>=0 || board[nx][ny]=='#'||board[nx][ny]=='F') continue;
            
            dist[nx][ny] = dist[cur.X][cur.Y]+1;
            Q.push({nx, ny});
            
        }
        
    }
    cout << "IMPOSSIBLE";
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> R>>C;
  int fi, fj;
  
  for(int i=0; i<R; i++){
      for(int j=0; j<C; j++){
          cin >> board[i][j];
          if(board[i][j]=='J') {
              dist[i][j]=0;
              Q.push({i, j});
          }
          if(board[i][j]=='F'){
              Q2.push({i,j});
              dist2[i][j]=0;
          }
      }
  }
  
  fire();
  bfs();
    

  return 0;
}

현재 코드에서 지훈이가 움직이고 불이 한칸만 움직이게 하려면 어떻게 해야할까? bfs 두개를 동시에 돌리는 방법을 모르겠다.

풀이 2 - 정답코드

결국 모르겠어서 정답코드를 확인했다.
정답 코드에서 가장 중요했던 부분은

if(dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.X][cur.Y]+1) continue; // 불의 전파 시간을 조건에 추가

이 부분이다. bfs를 동시에 돌리지 않고, 지훈이와 불에 대한 bfs를 따로 돌린 후, 각 dist에 저장된 거리(시간)를 비교하여 불이 지훈이보다 빨리 도달한 경우에는 해당 칸에 지훈이가 갈 수 없는 것이므로 continue를 해준다.

어떻게 이런 생각을...

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

char board[1001][1001];  
int dist[1001][1001];
int dist2[1001][1001];


int R, C;
queue<pair<int, int>> Q;
queue<pair<int, int>> Q2;

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

    cin >> R>>C;
    
  for(int i = 0; i < R; i++){
    fill(dist[i], dist[i]+C, -1);
    fill(dist2[i], dist2[i]+C, -1);    
  }
  
  cin >> R>>C;
  
  for(int i=0; i<R; i++){
      for(int j=0; j<C; j++){
          cin >> board[i][j];
          if(board[i][j]=='J') {
              dist[i][j]=0;
              Q.push({i, j});
          }
          if(board[i][j]=='F'){
              Q2.push({i,j});
              dist2[i][j]=0;
          }
      }
  }
  
  //불에대한 bfs
  while(!Q2.empty()){
        auto cur = Q2.front();
        Q2.pop();
        
        
        //상하좌우 확인하기
        for(int dir=0; dir<4; dir++){
            int nx = cur.first+dx[dir];
            int ny = cur.second+dy[dir];
            
            //범위 확인하기
            if(nx<0||ny<0||nx>=R||ny>=C) continue;
            //방문했거나 벽이면 pass
            if(dist2[nx][ny]>=0 || board[nx][ny]=='#') continue;
            
            dist2[nx][ny] = dist2[cur.X][cur.Y]+1;
            Q2.push({nx, ny});
            
        }
        
    }
    
    //사람에 대한 bfs
    while(!Q.empty()){
        auto cur = Q.front();
        Q.pop();
        
        
        //상하좌우 확인하기
        for(int dir=0; dir<4; dir++){
            int nx = cur.X+dx[dir];
            int ny = cur.Y+dy[dir];
            
            //범위 확인하기-> 범위 밖으로 나가면 탈출 성공
            if(nx<0||ny<0||nx>=R||ny>=C) {
                cout << dist[cur.X][cur.Y]+1; 
                return 0;
            }
            //방문했거나 벽이거나 불이 나 있으면 pass
            if(dist[nx][ny]>=0 || board[nx][ny]=='#') continue;
            if(dist2[nx][ny] != -1 && dist2[nx][ny] <= dist[cur.X][cur.Y]+1) continue; // 불의 전파 시간을 조건에 추가
            
            dist[nx][ny] = dist[cur.X][cur.Y]+1;
            Q.push({nx, ny});
            
        }
        
    }
    cout << "IMPOSSIBLE";

  return 0;
}