[백준] 불!

조금 변형된 유형의 문제를 찾아서 풀어봤다. 솔직히 이제 백준 그래프 추천 문제는 정말로 많이 풀게 된거같다. 이번 문제도 큰 문제없이 한번에 통과 됐고 설명에 대한 해석만 본 후에 잘 풀었다. 일반적으로 시뮬레이션이 섞인 BFS 탐색 문제에서 두 물체가 움직이게 되면 하나가 먼저 움직이고 다른 하나가 움직이기 나름인데 이 문제는 특이하게도 지훈이라는 캐릭터와 불이 난 공간이 동시에 움직여야 했다.

그러나 여기서 가장 고려해볼점은 지훈이는 절대로 불이 있는 곳으로 움직이지 못하지만 불은 움직이는데 벽 말고는 제한이 없단것이다. 그래서 내가 생각했던것은, 지훈이를 무시한채로 불을 먼저 움직이고 visited 벡터를 불과 지훈이한테 따로 만들어줘서 탐색하자 였다. 만약에 지훈이가 움직일 수 있는 공간이 없어지면 그 말은 탈출을 못했단 소리이기 때문에 IMPOSSIBLE 을 출력해줬다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int R, C; 
char matrix[1001][1001]; 
bool Jihoon[1001][1001];
bool Fire[1001][1001]; 
vector<pair<int,int>> dir = {{0,1},{0,-1},{1,0},{-1,0}}; 

struct Ji{
    int x, y, dist; 
};

void Input(){
    cin >> R >> C; 
    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            cin >> matrix[i][j]; 
        }
    }

}

void Solution(){
    queue<pair<int,int>> fireQ; 
    queue<Ji> JihoonQ; 

    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            if(matrix[i][j] == 'F'){
                Fire[i][j] = true; 
                fireQ.push({i,j}); 
            }
            if(matrix[i][j] == 'J'){
                Jihoon[i][j] = true; 
                JihoonQ.push({i,j,0}); 
            }
        }
    }

    while(!JihoonQ.empty()){
        int size1 = fireQ.size();
        int size2 = JihoonQ.size();
        for(int i = 0; i < size1; i++){
            pair<int,int> first = fireQ.front(); 
            fireQ.pop(); 

            int x = first.first, y = first.second; 

            for(pair<int,int>& p : dir){
                int nX = x + p.first;
                int nY = y + p.second; 

                if(nX < 0 || nY < 0 || nX >= R || nY >= C || matrix[nX][nY] == '#' || Fire[nX][nY]) continue;

                Fire[nX][nY] = true;
                fireQ.push({nX,nY}); 
            }
        }

        for(int j = 0; j < size2; j++){
            Ji second = JihoonQ.front();
            JihoonQ.pop(); 

            int xx = second.x, yy = second.y, dist = second.dist; 

            if(xx == R-1 || xx == 0 || yy == C-1 || yy == 0){
                cout << dist + 1; 
                return; 
            }

            for(pair<int,int>& p : dir){
                int nXX = xx + p.first;
                int nYY = yy + p.second;

                if(nXX < 0 || nYY < 0 || nXX >= R || nYY >= C || matrix[nXX][nYY] == '#' || Jihoon[nXX][nYY] || Fire[nXX][nYY]) continue;

                Jihoon[nXX][nYY] = true; 
                JihoonQ.push({nXX,nYY,dist+1}); 
            }
        }
        
    }

    cout << "IMPOSSIBLE"; 
}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}

하나의 while 문에서 두가지에 큐를 동시에 적은적은 처음이기에 그래도 재밌게 풀었지만 문제 설명을 좀 더 잘해줬으면 하는 바램은 있다.

배운점
1. 시뮬레이션 BFS.
2. 여러가지 visited 배열을 활용하자.