[ 백준 5427 ] 불 (C++)

백준의 불(5427) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) BFS문제에서 한 단계 더 생각해서 비교해야될 대상이 하나 더 있는 문제이다.

   사람이 불나는 건물에서 탈출을 해야 하는데, 불이 있는 곳으로는 사람이 갈 수 없을 뿐더러 불 또한 사람처럼 1초마다

   한 칸씩 번져나가게 된다.

   이러한 문제의 전체적인 문제 풀이 방식부터 알아보자.

   1. 불에 대한 맵을 하나 만든다.

     1-1) 특정 지점에, 불이 갈 수 있는 최단시간을 특정 지점의 값으로 설정해주기.

   2. 사람들 움직이는데, 불의 맵과 비교해서 더 빨리 갈 수 있는 곳으로만 움직여주기.

   핵심은 1번이다. 불의 맵을 만드는 것인데, 이 과정에 대해서 자세히 알아보자.

   위의 그림처럼 불이 저 좌표에 있을 경우를 생각해보자.

   1초 후에 불이 번져 나가는 곳은 위의 그림에서 숫자 1이 적힌 곳이고, 2초 후에 불이 번져 나가는 곳은 숫자 2가 적힌

   곳이 될 것이다. 이런식으로 불의 맵을 먼저 하나 작성하자.

   물론, 불의 위치가 한 곳이 아닌 여러 곳이 있을 수 있기 때문에, BFS-Leveling Skill을 통해서 구현해줘야 한다.

   BFS가 Queue의 Size만큼 반복하면서, 이동하려는 좌표 지점이 현재 값 + 1 을 한 값보다 더 크다면 값을 갱신해줘야 한다.

   구체적으로 알아보자 !

  

   불이 이렇게 있을 경우를 생각해보자. 불은 현재 (0, 0)과 (1, 2) 총 두 곳에 위치해 있고, 두 군데에서 동시에

   1초 마다 번져 나갈 것이다. 물론 현재 불이 있는 (0, 0)과 (1, 2)의 값은 0 이다.

   빈 칸에 들어갈 값들을 머릿속으로만 생각해보자. 정답은

   이러한 그림이 될 것이다. 그렇다면 여기서 파랑색으로 표시된 (0, 1) 지점에 주목해보자.

   (0, 1)의 경우 (0, 0)에 있는 불에 의해서 1초 후에 불이 번져질 것이다. 하지만, (1, 2)에 있는 불에 의해서는

   2초 후에 불이 번져지게 될 것이다. 위에 밑줄 그어놓은 말이 이 말이다.

   분명히 Queue를 돌리게 되면, (1, 2)에 있는 불에 의해서 (1, 1), (0, 2)는 1초라는 값으로 갱신될 것이고,

   (1, 1), (0, 2)에서 (0, 1)로 향하게 되는데, 이 떄 밑줄 쳐놓은 말에 대입시켜보면

   " 이동하려는 좌표인 (0, 1) 지점이 현재 값, 즉 (0, 2)와 (1, 1)의 값인 1 + 1을 한 값보다 더 크다면 값을 갱신한다"

   위의 경우는, 1 < 1 + 1 이므로 갱신을 해주지 않아도 된다는 의미이다.

   또한, 모든 값들을 갱신하기 위해서는 모든 정점의 초기 값을 무한대로 설정해 주어야 한다.

   생각 없이 0으로 초기화된 맵을 사용했다가는, 1초도 나오지 않게 될 것이다.

2) 이제 불의 맵을 다 완성했으니, 문제는 끝이 났다. 사람을 움직여 주면 되는데, 위에서 작성한 불의 맵과 시간을 비교해서

   더 작다면 움직여 주면 된다.

   불이 2초에 번지는 곳에, 사람이 3초에 갈 수는 없다. 즉, 불이 2초에 번지는 곳에 사람이 가려면 0초 혹은 1초에 그 지점을

   가줘야 하기 때문에, 불의 맵과 시간을 비교해서 더 작은 시간에 움직일 수 있는 좌표에 대해서만 사람을 움직여 줘야 하고

   탈출 할 수 있는 좌표에 도착한다면 시간을 출력 시켜 주면 된다.

   물론, 본인은 이 시간을 관리해주기 위해서 Queue를 int형 3개로 선언해 주었고, int형 3개의 의미는 (x좌표, y좌표, 시간)을

   의미한다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<queue>
 
#define endl "\n"
#define MAX 1000
#define INF 99999999
using namespace std;
 
int W, H;
int Fire_MAP[MAX][MAX];
int Person_MAP[MAX][MAX];
 
bool Visit[MAX][MAX];
char MAP[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
pair<int, int> Start;
queue<pair<int, int>> Fire_Q;
 
void Initialize()
{
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            Fire_MAP[i][j] = INF;
            Person_MAP[i][j] = INF;
        }
    }
 
    memset(Visit, false, sizeof(Visit));
}
 
void Input()
{
    cin >> W >> H;
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == '@')
            {
                Start.first = i;
                Start.second = j;
            }
            else if (MAP[i][j] == '*')
            {
                Fire_Q.push(make_pair(i, j));
                Fire_MAP[i][j] = 0;
            }
        }
    }
}
 
void Make_Fire_MAP()
{
    while (Fire_Q.empty() == 0)
    {
        int Qs = Fire_Q.size();
 
        for (int s = 0; s < Qs; s++)
        {
            int x = Fire_Q.front().first;
            int y = Fire_Q.front().second;
            Fire_Q.pop();
 
            for (int i = 0; i < 4; i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];
 
                if (nx >= 0 && ny >= 0 && nx < H && ny < W)
                {
                    if (MAP[nx][ny] != '#')
                    {
                        if (Fire_MAP[nx][ny] > Fire_MAP[x][y] + 1)
                        {
                            Fire_MAP[nx][ny] = Fire_MAP[x][y] + 1;
                            Fire_Q.push(make_pair(nx, ny));
                        }
                    }
                }
            }
        }
    }
}
 
void Print(int A[][MAX])
{
    cout << "###################################" << endl;
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            cout << A[i][j] << " ";
        }
        cout << endl;
    }
    cout << "###################################" << endl;
}
 
int Move_Person()
{
    queue<pair<pair<int, int>, int>> Q;
    Q.push(make_pair(make_pair(Start.first, Start.second), 0));
    Visit[Start.first][Start.second] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int Cnt = Q.front().second;
        Q.pop();
 
        if (x == H - 1 || x == 0 || y == W - 1 || y == 0) return (Cnt + 1);
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < H && ny < W)
            {
                if (MAP[nx][ny] == '.' && Visit[nx][ny] == false)
                {
                    if (Fire_MAP[nx][ny] > Cnt + 1)
                    {
                        Visit[nx][ny] = true;
                        Q.push(make_pair(make_pair(nx, ny), Cnt + 1));
                    }
                }
            }
        }
    }
    return -1;
}
 
void Solution()
{
    Make_Fire_MAP();
    //Print(Fire_MAP);
    int R = Move_Person();
    if (R == -1) cout << "IMPOSSIBLE" << endl;
    else cout << R << endl;
}
 
void Solve()
{
    int Tc;
    cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}