(BOJ) 5427 풀이

5427

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

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int fire[1002][1002], ar[1002][1002], visited[1002][1002];
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T, w, h, flag = 0;
    cin >> T;
    while (T--)
    {
        flag = 0;
        cin >> w >> h;
        for (int i = 0; i < h; i++)
        {
            fill(fire[i], fire[i] + w, -1);
            fill(visited[i], visited[i] + w, -1);
        }
        queue<pair<int, int>> Q;
        pair<int, int> start;
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                char c;
                cin >> c;
                if (c == '#')
                {
                    ar[i][j] = 0;
                }
                else if (c == '*')
                {
                    Q.push({i, j});
                    fire[i][j] = 0;
                    ar[i][j] = 1;
                }
                else if (c == '.')
                {
                    ar[i][j] = 1;
                }
                else
                {
                    start = {i, j};
                    ar[i][j] = 1;
                    visited[i][j] = 0;
                }
            }
        }
        while (!Q.empty())
        {
            pair<int, int> cur = Q.front();
            Q.pop();
            for (int i = 0; i < 4; i++)
            {
                int nx = dx[i] + cur.X;
                int ny = dy[i] + cur.Y;
                if (nx < 0 || ny < 0 || nx >= h || ny >= w || ar[nx][ny] != 1 || fire[nx][ny] != -1)
                    continue;
                fire[nx][ny] = fire[cur.X][cur.Y] + 1;
                Q.push({nx, ny});
            }
        }
        Q.push(start);
        while (!Q.empty() && flag == 0)
        {
            pair<int, int> cur = Q.front();
            Q.pop();
            for (int i = 0; i < 4; i++)
            {
                int nx = dx[i] + cur.X;
                int ny = dy[i] + cur.Y;
                if (nx < 0 || ny < 0 || nx >= h || ny >= w)
                {
                    flag = 1;
                    cout << visited[cur.X][cur.Y] + 1 << '\n';
                    break;
                }
                if (ar[nx][ny] != 1 || visited[nx][ny] != -1 || (visited[cur.X][cur.Y] + 1 >= fire[nx][ny] && fire[nx][ny]!=-1))
                    continue;
                visited[nx][ny] = visited[cur.X][cur.Y] + 1;
                Q.push({nx, ny});
            }
        }
        if (!flag)
            cout << "IMPOSSIBLE" << '\n';
    }
}

백준 고슴도치 문제랑 비슷한 문제다.

먼저 불의 모든 위치를 큐에 넣어서, BFS 를 돌린다.

그다음 큐가 비면, 사람 시작위치를 넣어서 BFS 를 돌린다.

사람이 맵을 벗어나면, 탈출에 성공한 것이므로 지금까지 걸린시간 + 1 을 출력해주고 반복문을 종료한다.

이동하려하는 곳까지 시간 < 이동하려는 곳까지 불 확산시간
위 조건을 만족해야 이동할 수 있는데,

불의 시간을 -1 으로 초기화 하므로, -1 일 때는 양수에서 조건을 만족할 수 없으므로

불이 퍼지지 않은 곳이면 (-1) 걸러야한다.