백준 4179 불! 풀이 (C++)

문제 링크

성능 요약

메모리: 10964 KB, 시간: 32 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2025년 2월 26일 14:25:58

문제 설명

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <tuple>

using namespace std;

int R, C;

char maze[1001][1001];
int Visited[1001][1001] = { 0, };
int VisitedFire[1001][1001] = { 0, };
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 };

int iStartY, iStartX;
vector<pair<int, int>> vFire;

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

    cin >> R >> C;
    for (int i = 0; i < R; ++i)
    {
        cin >> maze[i];
        for (int j = 0; j < C; ++j)
        {
            if (maze[i][j] == 'J')
            {
                iStartY = i;
                iStartX = j;
            }
            else if (maze[i][j] == 'F')
            {
                vFire.push_back({ i, j });
            }
        }
    }

    queue<pair<int, int>> Fq;
    for (auto fire : vFire)
    {
        Fq.push(fire);
        VisitedFire[fire.first][fire.second] = 1;
    }

    while (!Fq.empty())
    {
        int x, y;
        tie(y, x) = Fq.front();
        Fq.pop();

        for (int i = 0; i < 4; ++i)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || nx < 0 || ny >= R || nx >= C || maze[ny][nx] == '#')
                continue;
            if (VisitedFire[ny][nx] != 0)
                continue;

            VisitedFire[ny][nx] = VisitedFire[y][x] + 1;
            Fq.push({ ny, nx });
        }
    }

    queue<pair<int, int>> Jq;
    Jq.push({ iStartY, iStartX });
    Visited[iStartY][iStartX] = 1;

    while (!Jq.empty())
    {
        int x, y;
        tie(y, x) = Jq.front();
        Jq.pop();

        if (y == 0 || x == 0 || y == R - 1 || x == C - 1)
        {
            cout << Visited[y][x]; 
            return 0;
        }

        for (int i = 0; i < 4; ++i)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= R || nx >= C || maze[ny][nx] == '#' || Visited[ny][nx] != 0 || VisitedFire[ny][nx] != 0 && VisitedFire[ny][nx] <= Visited[y][x] + 1)
                continue;

            Visited[ny][nx] = Visited[y][x] + 1;
            Jq.push({ ny, nx });
        }
    }

    cout << "IMPOSSIBLE";
    return 0;
}

BFS 를 이용하여 풀이. 불기준 및  사람기준 둘다 BFS 를 해야한다. 그리고 메모리초과가 자주 떠서 조건을 까다롭게 하여 중복을 방지 하였다.