<백준> 5427 불 / C++ 풀이

중점:

1. 4179번 문제와 동일한 로직 사용

2. 이때 test case가 있기 때문에 break시에 queue를 초기화 해야한다.

3. bool 값을 이용해서 출력

---

정답 코드:

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second

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

string board[1002];
int vis1[1002][1002];
int vis2[1002][1002];

int t, w, h;

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

    cin >> t;

    while (t--)
    {
        cin >> w >> h;

        queue<pair<int, int> > Q1;
        queue<pair<int, int> > Q2;


        int result;
        bool escape = false;

        for (int i = 0; i < h; i++){
            cin >> board[i];

            fill(vis1[i], vis1[i] + w, -1);
            fill(vis2[i], vis2[i] + w, -1);

            for (int j = 0; j < w; j++){
                if (board[i][j] == '*'){
                    vis1[i][j] = 0;
                    Q1.push({i, j});
                }

                if (board[i][j] == '@'){
                    vis2[i][j] = 0;
                    Q2.push({i, j});
                }
            }
        }

        while (!Q1.empty())
        {
            auto cur = Q1.front();
            Q1.pop();

            for(int dir = 0; dir < 4; dir++){
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];

                if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
                if (vis1[nx][ny] >= 0 || board[nx][ny] == '#') continue;

                vis1[nx][ny] = vis1[cur.X][cur.Y] + 1;
                Q1.push({nx, ny});
            }
        }
        
        while (!Q2.empty() && !escape)
        {
            auto cur = Q2.front();
            Q2.pop();
            
            for (int dir = 0; dir < 4; dir++){
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];

                if (nx < 0 || nx >= h || ny < 0 || ny >= w){
                    escape = true;
                    result = vis2[cur.X][cur.Y] + 1;
                    break;
                }

                if (vis2[nx][ny] >= 0 || board[nx][ny] == '#') continue;
                if (vis1[nx][ny] != -1 && vis1[nx][ny] <= vis2[cur.X][cur.Y] + 1) continue;

                vis2[nx][ny] = vis2[cur.X][cur.Y] + 1;
                Q2.push({nx, ny});
            }
        }

        if (!escape){
            cout << "IMPOSSIBLE" << endl;
        } else {
            cout << result << endl;
        }
    }
}