5427번 불 - C++

✅️[문제]
https://www.acmicpc.net/problem/5427

5427번: 불

✅️[풀이]

BFS 문제이다!
불이 먼저 이동 하기 위해 불을 먼저 큐에 넣어두고, 상근이의 위치를 맨 나중에 넣어준다.
그리고 3차원 배열 vis를 통해 불의 이동과 상근이의 이동을 분리 시켜주고, 상근이가 가장자리에 도착했다면 vis값을 출력한 후 탈출시킨다.

✅️[코드]

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int vis[1003][1003][2];

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    
    
    while(n--){
        
        int w,h;
        cin >> w >> h;
        bool check = 0;
        string arr[1004];
        for(int i=0; i<h; i++){
            cin >> arr[i];
        }
        
        queue<pair<int,int>> q;
        int tmpx, tmpy;
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                if(arr[i][j] == '*') {
                    q.push({i,j});
                    vis[i][j][0] = 1;
                }
                else if(arr[i][j] == '@') {
                    tmpx = i, tmpy =j;
                }
            }
        }
        q.push({tmpx, tmpy});
        vis[tmpx][tmpy][1] = 1;
        while(!q.empty()){
            auto t = q.front(); q.pop();
            if(arr[t.X][t.Y] == '*'){
                for(int i=0; i<4; i++){
                    int x = t.X + dx[i];
                    int y = t.Y + dy[i];
                    
                    if(x<0 || x>=h || y<0 || y>=w) continue;
                    if(arr[x][y] != '.' || vis[x][y][0] > 0) continue;
                    vis[x][y][0] = 1;
                    arr[x][y] = '*';
                    q.push({x,y});
                }
            }
            else if(arr[t.X][t.Y] == '@'){
                if(t.X == 0 || (t.X == h-1) || (t.Y == 0) || (t.Y == w-1)) {
                    cout << vis[t.X][t.Y][1] << '\n';
                    check = 1;
                    break;
                }
                for(int i=0; i<4; i++){
                    int x = t.X + dx[i];
                    int y = t.Y + dy[i];
                    
                    if(x<0 || x>=h || y<0 || y>=w) continue;
                    if(arr[x][y] != '.' || vis[x][y][1] > 0) continue;
                    
                    vis[x][y][1] = vis[t.X][t.Y][1] +1;
                    arr[x][y] = '@';
                    q.push({x,y});
                }
            }
        }
            if(check == 0) cout << "IMPOSSIBLE" << '\n';
            memset(vis,0, sizeof(vis));
    }
}