BOJ - 5427 불

5427번 불

불이 초단위로 번지고, 상근이도 초단위로 칸을 움직인다.

상근이의 건물 탈출 가능성과 가능하다면 가장 빨리 탈출하는 시간을 구하는 문제이다.

문제 해결 과정

불과 상근이 모두 매 초 마다 상하좌우 네방향으로 움직일 수 있기 때문에 bfs를 적용하면 된다.

그러나 불이 번질 방향으로는 상근이가 움직일 수 없기 때문에 동시 적용이 아니라 불 먼저 적용 후 상근이를 적용한다.

불에 대한 bfs과정에서 Fire 배열에 불이 번진 시간을 저장한다.

상근이의 bfs과정에서 Fire 배열을 통해 불이 퍼진 시간과 상근이가 움직이는 시간을 비교하여 상근이의 움직임이 더 빠르다면 상근이가 움직일 수 있도록 한다.

그리고 테스트 케이스가 여러개 주어질 수 있기 때문에 매 과정이 끝난 후 사용된 배열과 큐들을 초기화 해준다.

코드

#include <iostream>
#include <queue>

using namespace std;
char arr[1001][1001] = {'.',};
int w,h;
int xpo[4] = {-1,1,0,0};
int ypo[4] = {0,0,-1,1};
int Fire[1001][1001];

int sol(queue<pair<pair<int,int>,int>> fire, queue<pair<pair<int,int>,int>> sg){

    while(!fire.empty() && !sg.empty()) {
        int fx = fire.front().first.first;
        int fy = fire.front().first.second;
        int fs = fire.front().second;

        fire.pop();

        for (int i = 0; i < 4; i++) {
            int nx = fx + xpo[i];
            int ny = fy + ypo[i];
            if (arr[nx][ny] == '#' || arr[nx][ny] == '*')
                continue;
            if (nx < 1 || nx > h || ny < 1 || ny > w)
                continue;
            fire.push(make_pair(make_pair(nx, ny), fs + 1));
            arr[nx][ny] = '*';
            Fire[nx][ny] = fs + 1;
        }
    }
    while(!sg.empty())
    {
        int sx = sg.front().first.first;
        int sy = sg.front().first.second;
        int ss = sg.front().second;

        if(sx == 1 || sx == h || sy == 1 || sy == w)
            return ss+1;
        sg.pop();

        for(int i=0;i<4;i++)
        {
            int nx = sx + xpo[i];
            int ny = sy + ypo[i];
            if(arr[nx][ny] == '#' || arr[nx][ny] == '@')
                continue;
            if(Fire[nx][ny] <= ss+1 && arr[nx][ny] == '*')
                continue;
            sg.push(make_pair(make_pair(nx,ny),ss+1));
            arr[nx][ny] = '@';
        }
    }
    return -1;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;
    for(int i=0;i<T;i++)
    {
        cin >> w >> h;
        queue<pair<pair<int,int>,int>> fire;
        queue<pair<pair<int,int>,int>> sg;
        for(int i=1;i<=h;i++)
        {
            for(int j=1;j<=w;j++)
            {
                cin >> arr[i][j];
                if(arr[i][j] == '@')
                {
                    sg.push(make_pair(make_pair(i,j),0));
                }
                else if(arr[i][j] == '*')
                {
                    fire.push(make_pair(make_pair(i,j),0));
                }
            }
        }

        int ans = sol(fire,sg);

        if(ans == -1)
            cout << "IMPOSSIBLE\n";
        else
            cout << ans << "\n";

        for(int i=1;i<=h;i++)
        {
            for(int j=1;j<=w;j++)
            {
                arr[i][j] = '.';
                Fire[i][j] = 0;
            }
        }
    }
    return 0;
}

생각해 볼 점

불에대한 bfs를 한 후 상근이에 대한 bfs를 하기 때문에 상근이가 빨리 탈출하는 경우 불이 더이상 번질 필요가 없기 때문에 시간적으로 손해를 보게 된다.

게다가 시간을 저장할 배열 역시 사용해야 하기 때문에 공간적으로도 손해를 보게 된다.

매 초마다 불을 상하좌우로 이동시킨 후 상근이를 상하좌우로 이동 하도록 한다면 상근이가 보다 빨리 탈출 하는 경우 시간적 손해를 방지할 수 있고, 기존에 주어진 맵에 대해 갱신만 하면 되므로 공간적 손해 역시 방지할 수 있다.

출처 : https://www.acmicpc.net/problem/5427