[백준 4179] 불!

 

불이랑 지훈이를 동시에 BFS 돌려줘야한다

불 BFS + 지훈 BFS가 한 턴인 것이다.

 

불을 먼저 돌려서 다음턴에 불이 붙을 곳을 미리 마킹에 반영해주고

그 뒤로 같은 턴인 지훈이를 옮길때

불이 붙을 곳을 미리 마킹해서 그 곳으로 지훈이를 못가게 해주면 된다.

 

지훈이의 BFS에 대해 방문한 곳은 방문하지 않게 하기 위해 visited 배열을 추가했다.

그럼 불에 대한 visited를 해야할까?

 

답은 필요없다 이다.

 

왜냐하면 현재 불이 번진 곳을 벽취급해서 지훈이가 아예 못가게 만들고 있는데,

// 불이면
if (cnt == -1)
{
    // 불 번진거는 벽취급해주기
    map[nexty][nextx] = 1;
    q.push(make_tuple(nexty, nextx, -1));
}

 

이를 통해 불이 지나간 곳도 그냥 벽으로 바꿔버리면

불은 벽인 곳을 지나가지 못하도록 되어있어 벽으로 바꿔버리는 것 자체가 방문처리까지 되어버리는 것이기 때문이다.

 

 

---

#include <iostream>
#include <queue>
#include <tuple>
#include <bitset>

#define SIZE 1001
using namespace std;

int R, C;
bitset<SIZE> map[SIZE];
bitset<SIZE> visited[SIZE];

int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};

int starty, startx;
vector<pair<int, int>> fire;

// 불이랑 지훈이는 동시에 움직임
// 불 움직임 + 지훈이 움직임 둘 다 해줘야하는게 한 턴임
// 불부터 움직이고 지훈이 움직이기
// 불 움직인 곳을 그냥 벽으로 만들기
void solve()
{
    queue<tuple<int, int, int>> q;
    for (int i = 0; i < fire.size(); i++)
    {
        q.push(make_tuple(fire[i].first, fire[i].second, -1));
    }
    q.push(make_tuple(starty, startx, 0));
    visited[starty][startx] = 1;

    while (!q.empty())
    {
        auto [y, x, cnt] = q.front();
        q.pop();

        // 지훈이가 가장자리 도착했으면 탈출한거임
        if (cnt >= 0 && (y == R - 1 || y == 0 || x == C - 1 || x == 0))
        {
            cout << cnt + 1;
            return;
        }

        int nexty, nextx;
        for (int i = 0; i < 4; i++)
        {
            nexty = y + dy[i];
            nextx = x + dx[i];

            // 범위 넘어가면 스킵
            if (nexty < 0 || nextx < 0 || nexty >= R || nextx >= C)
            {
                continue;
            }

            // 벽이면 무시
            if (map[nexty][nextx])
            {
                continue;
            }

            // 불이면
            if (cnt == -1)
            {
                // 불 번진거는 벽취급해주기
                map[nexty][nextx] = 1;
                q.push(make_tuple(nexty, nextx, -1));
            }
            // 지훈이면
            else
            {
                // 방문하지 않았다면
                if (!visited[nexty][nextx])
                {
                    // 방문 처리
                    visited[nexty][nextx] = 1;
                    q.push(make_tuple(nexty, nextx, cnt + 1));
                }
            }
        }
    }

    // queue 탐색 끝났는데도 return 안된거면 탈출 못한거
    cout << "IMPOSSIBLE";
}

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

    cin >> R >> C;

    char ch;
    for (int i = 0; i < R; i++)
    {
        for (int k = 0; k < C; k++)
        {
            cin >> ch;
            switch (ch)
            {
            case '#':
                map[i][k] = 1;
                break;
            case '.':
                map[i][k] = 0;
                break;
            case 'J':
                starty = i;
                startx = k;
                break;
            case 'F':
                map[i][k] = 1;
                fire.push_back(make_pair(i, k));
                break;
            default:
                // 처리할 필요 없는 문자일 경우
                break;
            }
        }
    }

    solve();

    return 0;
}

 

하고 싶은 말을 좀 덧붙이자면...

방화는 한 곳에서만 발생하는 줄 알았는데 불이 여러개일 수 있다한다...

이런건 기본적으로 문제에 적어줘야하는거 아닌가???