백준 4179 - 불!

문제 설명

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

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

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

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

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

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

https://www.acmicpc.net/problem/4179

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 미로의 상태가 주어지고 J의 위치에서 시작하여 불을 피해 미로를 탈출할 수 있는지를 알아내야 한다.

만약, 탈출할 수 있다면 최소 몇 번 움직이는지 알아야 한다.

 

문제를 해결하는 과정은 다음과 같다.

• 불이 번지는 것을 계산한다.
• 지훈이가 이동할 수 있는 지역으로 모두 이동해 본다.
• 만약, 미로를 탈출했다면 탐색을 종료한다.

 

우선, 불이 번지는 것은 일반적인 bfs와 동일하니 어렵지 않게 계산할 수 있다.

지훈이가 이동하는 것 역시 bfs 혹은 dfs로 계산할 수 있다.

하지만, 이 과정을 각각 처리하면 시간 초과 혹은 메모리 초과가 발생한다.

지훈이가 다른 곳으로 이동할 때마다 불이 번지는 것을 계산해야 하기 때문이다.

불이 번지는 것은 지훈이가 이동한 횟수에 고정이 된다.

즉, 지훈이가 1번 이동하면 불은 각 위치에서 1칸씩 번질 것이다.

따라서, 지훈이가 이동하는 횟수에 맞게 불이 번지는 것을 계산하도록 해야 한다.

그렇다면 bfs를 단계별로 진행하면 된다.

다음을 보면 단계별 bfs가 어떻게 동작하는지 알 수 있다.

지훈이가 움직이지 않으면 불은 F에만 존재한다.

지훈이가 한 번 움직이면 불은 한 칸씩 번져 주황색위치까지 존재한다.

즉, 지훈이의 움직임에 맞춰 불이 번지도록 계산하는 것이다.

현재 큐의 사이즈만큼만 bfs를 진행한 뒤, 새로 큐에 들어온 위치는 다음 단계에 진행하도록 하면 이를 구현할 수 있다.

while (!q.empty())
{
	int size = q.size();

	for(int i = 0 ; i < size; i++)
	{
    	//지훈 이동
	}
}

 

또한, 한 번 번진 불은 이미 주변에 불이 있기 때문에 더 이상 번질 일이 없다.

그렇기 때문에 불이 번지는 계산을 새로 번진 불에 대해서만 진행해도 된다.

//burn
while(!next.empty())
{
    auto [y, x] = next.front();
    next.pop();

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

        if (newY < 0 || newY >= R || newX < 0 || newX >= C) continue;
        if (maze[newY][newX] == '#') continue;
        if (maze[newY][newX] == 'F') continue;

        maze[newY][newX] = 'F';
        temp.push({ newY,newX });
    }
}

//지훈 이동
//...

next = move(temp);

 

즉, 정리해 보면 불은 지훈이의 이동 거리에 맞게 번지기 때문에 지훈이의 이동 단계별로 나눈 뒤 단계마다 한 번씩만 계산되도록 만들고 새로 번진 불에서만 다시 번지도록 계산하는 것이 핵심이다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int R, C;
int ans = INT_MAX;

vector<vector<bool>> visited;
vector<vector<char>> maze;
vector<pair<int,int>> fires;
pair<int, int> pos;

vector<int> dy = { -1, 0, 1, 0 };
vector<int> dx = { 0, 1, 0, -1 };

void bfs()
{
    queue<pair<int, int>> q;
    queue<pair<int, int>> next;
    q.push(pos);
    for (auto& fire : fires) next.push(fire);

    int level = 1;

    while (!q.empty())
    {
        int size = q.size();
        queue<pair<int, int>> temp;

        //burn
        while(!next.empty())
        {
            auto [y, x] = next.front();
            next.pop();

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

                if (newY < 0 || newY >= R || newX < 0 || newX >= C) continue;
                if (maze[newY][newX] == '#') continue;
                if (maze[newY][newX] == 'F') continue;

                maze[newY][newX] = 'F';
                temp.push({ newY,newX });
            }
        }

        for (int s = 0; s < size; s++)
        {
            auto [y, x] = q.front();
            q.pop();

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

                if (newY < 0 || newY >= R || newX < 0 || newX >= C)
                {
                    ans = min(ans, level);
                    return;
                }
                if (maze[newY][newX] == 'F') continue;
                if (maze[newY][newX] == '#') continue;
                if (visited[newY][newX]) continue;

                visited[newY][newX] = true;
                q.push({ newY, newX });
            }
        }

        level++;
        next = move(temp);
    }
}

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

	int answer = 0;
    cin >> R >> C;

    maze.resize(R, vector<char>(C));
    visited.resize(R, vector<bool>(C, false));

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

    visited[pos.first][pos.second] = true;

    bfs();
    
    if (ans == INT_MAX) cout << "IMPOSSIBLE";
    else cout << ans;

    return 0;
}

---