백준 / 바킹독님의 문제집 / 불!(4179)

문제 설명

 

 

문제 해결

 

불에 대한 BFS를 돌려서 불이 어떤 좌표에 얼마나 많은 시간이 지나서야 붙는지 저장하고

거기서 구한 데이터를 이용해 지훈이로 BFS를 돌려서 탈출에 얼마나 시간이 걸리는지 계산한다.

지훈이로 BFS를 돌릴 때 어떤 조건을 줘야 잘 돌아갈지 많이 고민했다.

 

#include <iostream>
#include <queue>
#include <utility>
#include <tuple>
#include <string>

using namespace std;

#define x first
#define y second

string map[1000];
int fire[1000][1000];
int human[1000][1000];

int main(int argc, char* argv[])
{

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int R, C;
    cin >> R >> C;

    queue<pair<int, int>> human_queue;
    queue<pair<int, int>> fire_queue;
    for (int i = 0; i < R; i++)
    {
        cin >> map[i];
        for (int j = 0; j < C; j++)
        {
            fire[i][j] = human[i][j] = -1;
            if (map[i][j] == 'J')
            {
                fire[i][j] = human[i][j] = 0;
                human_queue.push(make_pair(i, j));
            }
            else if (map[i][j] == 'F')
            {
                fire[i][j] = human[i][j] = 0;
                fire_queue.push(make_pair(i, j));
            }
        }
    }

    pair<int, int> direction[4] = { make_pair(1,0),make_pair(0,1),make_pair(-1,0),make_pair(0,-1) };

    while (!fire_queue.empty())
    {
        auto current = fire_queue.front();
        fire_queue.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = current.x + direction[i].x;
            int ny = current.y + direction[i].y;

            if (nx < 0 || nx >= R || ny < 0 || ny >= C)
                continue;
            if (fire[nx][ny] >= 0 || map[nx][ny] == '#')
                continue;

            fire[nx][ny] = fire[current.x][current.y] + 1;
            fire_queue.push(make_pair(nx, ny));
        }
    }

    while (!human_queue.empty())
    {
        auto current = human_queue.front();
        human_queue.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = current.x + direction[i].x;
            int ny = current.y + direction[i].y;

            if (nx < 0 || nx >= R || ny < 0 || ny >= C)
            {
                cout << human[current.x][current.y] + 1 << '\n';

            if (human[nx][ny] >= 0 || map[nx][ny] == '#')
                continue;

            if (fire[nx][ny] != -1 && fire[nx][ny] <= human[current.x][current.y] + 1) 
                continue;

            human[nx][ny] = human[current.x][current.y] + 1;
            human_queue.push(make_pair(nx, ny));
        }
    }

    cout << "IMPOSSIBLE" << '\n';

    return 0;
}