불 5427

문제

접근 방법

불!문제와 동일한 문제이지만 조금은 다르다.
1. 테스트케이스가 여러 개라는 점
2. 그렇기에 줄 바꿈이 있어야 한다는 점
3. 1001이 존재할 수 있다는 점 (미로와 같은 형태)
그렇기에 불!에서 사용했던 코드를 그대로 가져와서는 안 됐다. 조금 수정해야 했다.

코드

#include <iostream>
#include <queue>
#include <string>
#include <climits>
using namespace std;
int map[1001][1001];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    cin >> T;
    queue<pair<int, int>> fire, human, goal;
    while (T--)
    {
        fire = human = goal = queue<pair<int, int>>();
        int w, h, ret = INT_MAX;
        cin >> w >> h;
        for (int i = 0; i < h; ++i)
        {
            string k;
            cin >> k;
            for (int j = 0; j < w; ++j)
            {
                if (k[j] == '#')
                    map[i][j] = INT_MAX;
                else if (k[j] == '.')
                    map[i][j] = 0;
                else if (k[j] == '*')
                {
                    map[i][j] = -1;
                    fire.push({i, j});
                }
                else
                {
                    if (i == 0 || j == 0 || i == h - 1 || j == w - 1)
                        ret = 1;
                    map[i][j] = 1;
                    human.push({i, j});
                }
            }
        }
        if (ret == 1)
        {
            cout << 1 << "\n";
            continue;
        }
        while (!human.empty())
        {
            auto cur = human.front();
            human.pop();
            for (int i = 0; i < 4; ++i)
            {
                pair<int, int> next = {cur.first + dy[i], cur.second + dx[i]};
                if (next.first < 0 || next.second < 0 || next.first >= h || next.second >= w)
                    continue;
                if (map[next.first][next.second])
                    continue;
                if (next.first == 0 || next.second == 0 || next.first == h - 1 || next.second == w - 1)
                    goal.push(next);
                map[next.first][next.second] = map[cur.first][cur.second] + 1;
                human.push(next);
            }
        }
        while (!fire.empty())
        {
            auto cur = fire.front();
            fire.pop();
            for (int i = 0; i < 4; ++i)
            {
                pair<int, int> next = {cur.first + dy[i], cur.second + dx[i]};
                if (next.first < 0 || next.second < 0 || next.first >= h || next.second >= w)
                    continue;
                if (map[next.first][next.second] == INT_MAX)
                    continue;
                if (map[next.first][next.second] < abs(map[cur.first][cur.second] - 1))
                    continue;
                map[next.first][next.second] = map[cur.first][cur.second] - 1;
                fire.push(next);
            }
        }
        while (!goal.empty())
        {
            auto cur = goal.front();
            goal.pop();
            int number = map[cur.first][cur.second];
            if (number > 0)
            {
                if (ret > number)
                    ret = number;
            }
        }
        if (ret == INT_MAX)
            cout << "IMPOSSIBLE";
        else
            cout << ret;
        cout << "\n";
    }
    return 0;
}

풀이

처음부터 탈출할 수 있는 지점이면 출력해주고 continue를 해주었다. 그것이 문제였다. 줄 바꿈 없이 continue를 해주니 오답이 계속 나왔다.
생각보다 허무한 부분에서 실수했기에 아쉬웠다.
다른 사람들의 풀이를 보면 불을 먼저 지르고 사람이 다닐 수 있는지 확인하는 방식이었다. 그 방법이 더 효율적인 것 같으면서도 불은 사람을 뚫고 갈 수 있기에 별도로 사람의 최소 거리를 저장하고 있는 점은 아쉬웠다.