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

✍️ 첫번째 접근

'4179번 불!' 문제와 마찬가지로 BFS를 적용하면 손쉽게 풀 수 있다.
상근이에 대한 BFS와 불에 대한 BFS를 돌리면 되는데,
필자는 상근이에 대한 BFS를 돌리는 과정에서 상근이가 위치한 곳에 이미 불이 존재하거나 또는 상근이가 그 위치에 도착한 동시에 불도 도착한다는 조건을 오타로 인해 애를 먹었다.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[1002][1002];
int dist1[1002][1002];
int dist2[1002][1002];
int t,w,h;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--) {
        bool flag = false;
        queue<pair<int,int> > Q1;
        queue<pair<int,int> > Q2;
        cin >> w >> h;
        for(int i = 0; i < h; i++) {
            fill(dist1[i],dist1[i]+w,0);
            fill(dist2[i],dist2[i]+w,0);
        }
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                char c;
                cin >> c;
                if(c == '#')
                    board[i][j] = -1;
                else {
                    if(c == '*') {
                        Q1.push(make_pair(i,j));
                        dist1[i][j] = 1;
                    }
                    else if(c == '@') {
                        Q2.push(make_pair(i,j));
                        dist2[i][j] = 1;
                    }
                    board[i][j] = 0;
                }
            }
        }
            // 불에 대한 bfs
            while(!Q1.empty()) {
                pair<int,int> 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(board[nx][ny] == -1)
                        continue;
                    if(dist1[nx][ny])
                        continue;
                    dist1[nx][ny] = dist1[cur.X][cur.Y] + 1;
                    Q1.push(make_pair(nx,ny));
                }
            }
            // 상근이에 대한 bfs
            while((!Q2.empty()) && (!flag)) {
                pair<int,int> 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) {
                        cout << dist2[cur.X][cur.Y] << '\n';
                        flag = true;
                        break;
                    }
                    if(board[nx][ny] == -1)
                        continue;
                    if(dist2[nx][ny])
                        continue;
                    if(dist1[nx][ny] != 0 && dist1[nx][ny] <= dist2[cur.X][cur.Y] + 1)
                        continue;
                    dist2[nx][ny] = dist2[cur.X][cur.Y] + 1;
                    Q2.push(make_pair(nx,ny));
                }
            }
            if(!flag) {
                cout << "IMPOSSIBLE" << '\n';
                continue;
            }
        }

    return 0;
}