백준, BOJ, 4179번 C++ [CPP]

 

BFS의 응용문제다.

어렵진 않지만 응용하는 첫번째 단계라고 할 수 있다.

 

 

www.acmicpc.net/problem/4179

4179번: 불!

 

---

이 문제도 BFS를 이용한다는 감이 온다.

 

고려해야 할 조건이 몇가지 있다.

 

1. 지훈이의 탈출 조건

2. 불이 있는 곳에 지훈이 있을 수 없다.

 

우선 지훈이는 문제에서 가장자리에 있으면 탈출 할 수 있다.

즉, [ i ][ j ] 위치에서 i 또는 j 가 0을 가지거나 최댓값을 가지면 탈출한 것이다.

-> 다시 말해서 가장자리에 도착할 때 BFS 단계 + 밖으로 나가는 시간(1)을 포함해서 계산이 가능하다.

 

불이 있는 곳에 지훈이 갈 수 없다는 말은 무엇이냐면

같은 BFS 단계에는 갈 수 없다는 말이다.

 

불도 BFS 2단계에 퍼지고 지훈도 2단계에 걸쳐서 갈 수 있으면 지훈은 그곳에 갈 수 없다.

즉, 불의 BFS의 결과가 지훈의 움직임에 영향을 미친다.

 

 

---

# 맞은 풀이

#include<iostream>
#include<queue>
#include<algorithm> // fill

using namespace std;

#define X first // column
#define Y second // row

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

string maze[1002]; // 공백이 없어서 string으로 받는다.

// 불의 BFS결과가 지훈에게 영향을 주기 때문에 2개 이용
int visJ[1002][1002]; // 지훈
int visF[1002][1002];// 불

int m,n;


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    queue<pair<int,int>> QJ;
    queue<pair<int,int>> QF;
    
    //행, 열 차례대로 입력
    cin>> m >> n;
    
    // 미로를 string으로 받음
    for(int i = 0; i < m; i++){
        cin>> maze[i];
    }
    
    // 거리초기화(단계 초기화)
    for(int i = 0; i < m; i++){
        fill(visJ[i], visJ[i]+n, -1);
        fill(visF[i], visF[i]+n, -1);
    }
    
    
    //시작점 찾기 -  불, 지훈
    for(int i = 0; i<m; i++){
        for(int j = 0; j<n; j++){
            if(maze[i][j] == 'F'){
                QF.push({i,j});
                visF[i][j] = 0;
            }else if(maze[i][j] == 'J'){
                QJ.push({i,j});
                visJ[i][j] = 0;
            }
        }
    }
    
    
    
    //불 BFS 돌림 
    while(!QF.empty()){
        auto cur = QF.front();
        QF.pop();
        for(int dir = 0; dir < 4; dir++){
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if(nx < 0 || nx >= m || ny < 0 || ny >= n)
                continue;
            if(visF[nx][ny] >= 0 || maze[nx][ny] == '#')
                continue;
            visF[nx][ny] = visF[cur.X][cur.Y] + 1; // 단계 
            QF.push({nx,ny});
        }
    }
    
    
    
    //불 BFS 결과 이후 지훈 BFS 돌림  -> 만약 불이 났다면 지훈은 통과하지 못함.
    while(!QJ.empty()){
        auto cur = QJ.front();
        QJ.pop();
        
        for(int dir = 0; dir < 4; dir++){
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            
            //이 if문에 들어온다는 것은 지훈이 가장자리에 있다는 뜻
            if(nx < 0 || nx >= m || ny < 0 || ny >= n){
                cout << visJ[cur.X][cur.Y]+1;
                return 0;
                }
            if(visJ[nx][ny] >= 0 || maze[nx][ny] == '#')
                continue;
            
            // 지훈이가 가려는 시간 전에 불이 퍼지면 못감.
            // 다시 말해서 불의 BFS 단계가 더 커야함. 같아도 안된다.
            if(visF[nx][ny] != -1 && visF[nx][ny] <= visJ[cur.X][cur.Y] + 1)
                continue;
            
            
            visJ[nx][ny] = visJ[cur.X][cur.Y] + 1; // 지훈이 가려는 곳임.
            QJ.push({nx,ny});
        }
    }
    cout << "IMPOSSIBLE" ;  // 여기까지오면 탈출 실패

    
}

 

 

BFS를 따로 돌리는 것이 핵심 그리고

지훈이가 BFS에 따라 움직임이 제한되는 것이 문제의 핵심이다.

 

저 마지막 조건을 다시 풀어보면서 완전히 이해해야 하니 나도 다시 풀어봐야 한다.