백준, BOJ, 5427번, 불 C++ [CPP] ★★★★★★

BFS 중에서 가장 재밌는 유형이면서 가장 까다롭다.

조건이 별로 없어서 다행이지.. 여러개면 진짜 한없이 어려워진다.

가장 중요한 문제가 아닌가 싶다.

이 문제를 잘 풀줄 알면.. 다른 것도 잘풀 걸..?

 

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

 

---

 

#맞는 풀이

#include <bits/stdc++.h>

using namespace std;

int dc[4] = {-1,1,0,0};
int dr[4] = {0,0,-1,1};


char board[1002][1002];
int test[1002][1002]; //불 위치,  0 빈공간, -1 불이 갈 수 없는 공간
int live[1002][1002]; //상근이 탈출

int main(){
    int testcase;
    cin >> testcase;
    
    //맵이 크기 상근이를 옮기면서 불을 옮기는 것보다는
    //불을 이미 다 지르고 나서 상근이가 갈 수 있나 확인해본다.
    while(testcase--){
        int w,h;
        cin >> w >> h;  //w는 열(column)    h는 행(row)
        
        //상근이 위치
        int r, c;
        
        //자꾸 공백을 입력받아서 오류생김
        string str;
        getline(cin, str);
        
        //불의 BFS를 위함
        queue<pair<int,int>> fires;
        
        //공백없이 주어진 입력 [행, 열 순]
        for(int i = 0; i<h; i++){
            string line;
            getline(cin, line);
            for(int j = 0; j<w; j++){
                board[i][j] = line[j];
                
                //테스트 이후초기화 해야함 중요!!!
                live[i][j] = 0;

                //상근이 위치
                if(board[i][j] == '@'){
                    r = i;
                    c = j;
                    test[i][j] = 0;
                }else if(board[i][j] == '#'){
                    test[i][j] = -1;
                }                
                else if(board[i][j] == '.'){
                    test[i][j] = 0;
                }else if(board[i][j] == '*'){
                    test[i][j] = 1; //test[i][j] : 불이 붙는 시간 ( > 0)
                    fires.push({i,j});
                }
            }
        }

        //불이 붙는 시간을 BFS로 계산
        while(!fires.empty()){
            auto cur = fires.front();
            fires.pop();
            for(int dir = 0; dir<4; dir++){
                int nr = dr[dir] + cur.first;
                int nc = dc[dir] + cur.second;
                
                if(nr < 0 || nc < 0 || nr >= h || nc >= w)continue;
                if(test[nr][nc] == 0){
                    test[nr][nc] = test[cur.first][cur.second] + 1;
                    fires.push({nr,nc});
                }
            }
        }

        //상근이의 BFS를 위함
        queue<pair<int,int>> q;
        q.push({r,c});
        live[r][c] = 1;
        bool isOut = false;
        
        
        while(!q.empty()){
            auto cur = q.front();
            q.pop();
            
            for(int dir = 0; dir<4; dir++){
                int nr = cur.first + dr[dir];
                int nc = cur.second + dc[dir];
                
                //탈출가능하면
                if(nc < 0 || nc >= w || nr < 0 || nr >= h){
                    cout << live[cur.first][cur.second] << '\n';
                    isOut = true;
                    break; //이건 for문만 나간다.
                }
                //이미 방문했으면
                if(live[nr][nc] > 0)continue;
                if(test[nr][nc] == -1)continue;
                
                //불보다 빨리 방문 가능하거나 불이 없는 공간일 경우
                if(test[nr][nc] > live[cur.first][cur.second] + 1 || test[nr][nc] == 0){
                    live[nr][nc] = live[cur.first][cur.second] + 1;
                    q.push({nr,nc});
                }
            }
            if(isOut)break; //while문을 나가야함
        }
        
        if(!isOut){
            cout << "IMPOSSIBLE" << '\n';
        }
        
    }
    
    return 0;
}