BOJ 5427 C++

코드

#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define X first
#define Y second

// 방향성 배열
int dx[4] = { 1, 0, -1, 0 }; // 상하좌우 방향에 대한 x좌표 설정
int dy[4] = { 0, 1, 0, -1 }; // 상하좌우 방향에 대한 y좌표 설정

string board[1001]; // 건물 지도를 나타내는 문자열 배열
int fire[1001][1001]; // 불이 몇 초 후에 전파되는지 저장하는 배열
int sang[1001][1001]; // 상근이가 몇 초 만에 이동하는지 저장하는 배열

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    // 테스트 케이스 수 입력
    int t; cin >> t;
    while (t--)
    {
        int w, h; cin >> w >> h;

        // 불과 상근이의 위치를 저장할 큐 선언
        queue<pair<int, int>> st, f;

        // 빌딩 지도를 입력받고, 초기화 작업 수행
        for (int i = 0; i < h; i++)
        {
            cin >> board[i];
            fill(fire[i], fire[i] + w, -1);
            fill(sang[i], sang[i] + w, -1);
            for (int j = 0; j < w; j++)
            {
                if (board[i][j] == '@') // 상근이 위치를 큐에 삽입하고 상근 배열을 0으로 초기화
                {
                    sang[i][j] = 0;
                    st.push({ i,j });
                }

                if (board[i][j] == '*') // 불의 위치를 큐에 삽입하고 불 배열을 0으로 초기화
                {
                    fire[i][j] = 0;
                    f.push({ i,j });
                }
            }
        }

        // 불에 대한 확산 시뮬레이션(Breadth-First Search) 실행
        while (!f.empty())
        {
            auto cur = f.front(); f.pop();
            
            // 사방으로 확산하는 과정
            for (int dir = 0; dir < 4; dir++)
            {
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];

                // 벽을 넘어가지 않는 경우 확인
                if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
                // 이동할 위치가 빈 칸이고 불이 아직 전파되지 않은 경우
                if (board[nx][ny] != '.' || fire[nx][ny] >= 0) continue;

                // 불이 확산되는 시간 설정
                fire[nx][ny] = fire[cur.X][cur.Y] + 1;
                f.push({ nx,ny });
            }
        }

        bool ex = 0; // 탈출 여부 변수
        // 상근이가 벽을 향해 이동하는 시뮬레이션 실행
        while (!st.empty())
        {
            auto cur = st.front(); st.pop();
            for (int dir = 0; dir < 4; dir++)
            {
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];

                // 경계를 벗어난다면 탈출 시간 출력 후 break
                if (nx < 0 || ny < 0 || nx >= h || ny >= w)
                {
                    ex = 1;
                    cout << sang[cur.X][cur.Y] + 1 << "\n";
                    break;
                }

                // 이동할 위치가 빈 칸이고 상근이가 아직 이동하지 않은 경우
                if (board[nx][ny] != '.' || sang[nx][ny] >= 0) continue;
                // 이동할 위치의 불 전파 시간이 이동 시간보다 빠른 경우, 이동할 수 없음.
                if (fire[nx][ny] <= sang[cur.X][cur.Y] + 1 && fire[nx][ny] != -1) continue;

                // 상근이가 이동하는 시간 설정
                sang[nx][ny] = sang[cur.X][cur.Y] + 1;
                st.push({ nx,ny });
            }
            if (ex) break; // 출구를 찾았다면 루프 종료
        }

        if (ex != 1) // 탈출이 불가능 경우 "IMPOSSIBLE" 출력
            cout << "IMPOSSIBLE\n";
    }
    return 0;
}

불 bfs는 그냥 돌리면 되고 상근이의 이동에서 예외 처리가 중요한 문제였다.

 if (fire[nx][ny] <= sang[cur.X][cur.Y] + 1 && fire[nx][ny] != -1) continue;

여기서&& fire[nx][ny] != -1인 이유는 처음에 -1로 도착안했음을 초기화했기에 이 예외처리를 안하면 불의 이동시간이 상근이의 다음 이동시간보다 항상 작기때문.