[Problem Solving] BOJ 5427 : 불

문제 링크 : https://www.acmicpc.net/problem/5427

 

건물에서 탈출해야 하는 데, 불이 탈출구까지 번지기 전에 탈출할 수 있는지, 그렇다면 최소 몇 초만에 탈출할 수 있는지 구하는 문제이다.

 

1. 사람에 대한 BFS를 수행하여, 사람이 처음 존재하는 격자에서 다른 격자까지 가는데 걸리는 최소 시간을 각 격자마다 구한다. 사람은 불이 최초로 난 곳과 벽을 제외한 모든 곳으로 움직일 수 있다.

2. 불에 대한 BFS를 수행하여, 불이 있는 곳으로 부터 각 격자마다 번지게 되는 최소 시간을 계산한다. 불은 벽을 제외한 모든 곳에 번질 수 있다.

3. 건물의 탈출구까지 불이 번지기 전에 지훈이가 도달할 수 있는 경우, 도달할 수 있는 시간 중 최소 시간을 구해서 출력한다. 그렇지 못한다면 IMPOSSIBLE을 출력한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <algorithm>
#define endl '\n'
using namespace std;

struct Point
{
    int y;
    int x;
};

int T;
int w, h;
char Map[1001][1001];
int fireDist[1001][1001];
int humanDist[1001][1001];
vector<Point> fireLocations;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
int answer = 987654321;

void input()
{
    cin >> w >> h;
    fill(&fireDist[0][0], &fireDist[h - 1][w], 987654321);
    fill(&humanDist[0][0], &humanDist[h - 1][w], 987654321);
    for (int i = 0; i < h; i++)
    {
        string row;
        cin >> row;
        for (int j = 0; j < w; j++)
        {
            Map[i][j] = row[j];
        }
    }
}

bool valid(int y, int x)
{
    return (0 <= y && y < h && 0 <= x && x < w);
}

void humanBfs(Point s)
{
    queue<Point> q;
    q.push(s);
    while (!q.empty())
    {
        Point cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            Point next = {cur.y + dy[i], cur.x + dx[i]};
            if (valid(next.y, next.x) && Map[next.y][next.x] == '.' && humanDist[next.y][next.x] > humanDist[cur.y][cur.x] + 1)
            {
                humanDist[next.y][next.x] = humanDist[cur.y][cur.x] + 1;
                q.push(next);
            }
        }
    }
}

void fireBfs(Point s)
{
    queue<Point> q;
    q.push(s);
    while (!q.empty())
    {
        Point cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            Point next = {cur.y + dy[i], cur.x + dx[i]};
            if (valid(next.y, next.x) && Map[next.y][next.x] != '#' && fireDist[next.y][next.x] > fireDist[cur.y][cur.x] + 1)
            {
                fireDist[next.y][next.x] = fireDist[cur.y][cur.x] + 1;
                q.push(next);
            }
        }
    }
}

void solution()
{
    Point s;
    fireLocations.resize(0);
    answer = 987654321;
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            if (Map[i][j] == '@')
            {
                humanDist[i][j] = 0;
                s = {i, j};
            }
            else if (Map[i][j] == '*')
            {
                fireDist[i][j] = 0;
                fireLocations.push_back({i, j});
            }
        }
    }

    humanBfs(s);
    for (auto fireLocation : fireLocations)
    {
        fireBfs(fireLocation);
    }

    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            if (!(i == 0 || j == 0 || i == h - 1 || j == w - 1))
                continue;
            if (humanDist[i][j] < fireDist[i][j])
            {
                answer = min(answer, humanDist[i][j] + 1);
            }
        }
    }
}

void output()
{
    if (answer == 987654321)
        cout << "IMPOSSIBLE" << endl;
    else
        cout << answer << endl;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> T;
    while (T--)
    {
        input();
        solution();
        output();
    }
    return 0;
}