[ 백준 4179 ] 불 ! (C++)

백준의 불!(4179) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 이러한 문제는 크게 2단계로 나누어서 풀면 쉽게 구현할 수가 있다.

   1. 불의 맵 만들기 !

   2. 사람 움직여주기 !

   위의 2단계면 쉽게 구현할 수 있는 문제이다. 먼저, 불의 맵부터 만드는 방법을 구체적으로 알아보자.

   본인은, 입력받는 맵 이외에도, 불이 퍼져나가는 시간을 저장해주는 int Fire_MAP[][] 이라는 2차원 맵을 하나 더 만들어 주었다.

   Fire_MAP의 초기값은 무한대이며, 입력 시, 불이 있는 곳의 좌표만 0으로 설정해주고, Queue에 넣어주었다.

   왜냐하면, 입력 시 불이 있는 곳은 0초에 불이 존재할 수 있는 곳이라는 의미이고, Queue에 넣어준 이유는, 불이 한 곳에서만

   존재하는 것이 아닌, 여러 곳에서 존재할 수 있기 때문이다.

   이후에, 불의 맵을 채워주면 된다. 맵에서 '#' 으로 표시되는 갈 수 없는 공간은 무한대로 내버려둬도 상관이 없다.

   불의 맵을 채우는 방법은 간단하다. 일반적인 BFS처럼 Queue를 반복시켜 주는데, 탐색하고자 하는 정점의 시간이, 현재 정점의

   시간 + 1 보다 더 크다면 채워주면 된다.

  

    예를 들어서 이러한 불의 맵이 있다고 가정해보자. 0으로 표시된 곳은, 입력 시 초기에 불이 있던 위치이고, 나머지는 위에서

    말한대로 무한대로 채워놓은 상태이다.

    여기서, 1초가 지나면 어떻게 될까 ?? 아마, 파랑색으로 표시된 곳이 1로 바뀔 것이다. 왜냐하면, 불은 1초마다 상하좌우로 퍼져

    나갈 수 있기 떄문이다.

    즉, 탐색하고자 하는 정점의 시간이(INF) 현재 정점의 시간 + 1 (0 + 1 ) 보다 더 컸기 때문에, 더 작은 값으로 바꿔준 것이다.

    이런식으로, 불의 맵을 만들어 주면 된다. 불의 맵을 만드는 코드는 아래와 같다.

void Make_Fire_Map(int a, int b)
{
    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 < R && ny < C)
                {
                    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));
                        }
                    }
                }
            }
        }
    }
}

     이제 불의 맵을 다 만들었다면, 사람을 움직여 주기만 하면 된다. 사람을 움직일 때는 불의 맵과 비교를 해줘야 한다.

     사람이 특정 좌표에 움직이려고 할 때, 그 좌표의 불의 시간이 더 크다면 움직일 수 있는 것이다.

   

     위의 경우는, 사람과 불의 위치가 주어졌을 때 갈 수 있는 시간을 표시한 것이다.

     파랑색 = 사람의 시간, 빨강색 = 불의시간 을 의미한다.

     가장 왼쪽 위의 좌표인 (0 , 0)을 한번 보자. 사람은 1초만에 갈 수 있는 좌표이지만, 불은 2초가 되야 저 정점에 도달할 수 있다.

     즉, 사람의 움직이려고 하는 시간보다 불의 시간이 더 크기 때문에 사람은 (0 , 0)으로 갈 수 있는 것이다.

     반대로 ( 0 , 1)을 한번 봐보자. 사람은 2초만에 갈 수 있는 좌표이지만, 불은 1초만에 갈 수 있다.

     따라서 사람은 저 좌표에는 갈 수 없다는 것을 의미한다.

  

     사람을 움직이는 BFS 함수 안에서는 위에서 말한 부분을 신경쓰면서 구현해 주면 된다.

[ 소스코드 ]

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 1000
using namespace std;
 
int R, C;
char MAP[MAX][MAX];
int Fire_MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
pair<int, int> Start, Fire;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
queue<pair<int, int>> Fire_Q;
 
void Input()
{
    cin >> R >> C;
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            bool Fire = false;
            cin >> MAP[i][j];
            if (MAP[i][j] == 'J')
            {
                Start.first = i;
                Start.second = j;
            }
            else if (MAP[i][j] == 'F')
            {
                Fire_Q.push(make_pair(i, j));
                Fire_MAP[i][j] = 0;
                Fire = true;
            }
            if(Fire == false) Fire_MAP[i][j] = 987654321;
        }
    }
}
 
void Make_Fire_Map(int a, int b)
{
    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 < R && ny < C)
                {
                    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));
                        }
                    }
                }
            }
        }
    }
}
 
int Move_Person(int a, int b)
{
    queue<pair<pair<int, int>, int>> Q;
    Q.push(make_pair(make_pair(a, b), 0));
    Visit[a][b] = 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 == 0 || y == 0 || x == R - 1 || y == C - 1) 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 < R && ny < C)
            {
                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(Fire.first, Fire.second);
    int R = Move_Person(Start.first, Start.second);
    if (R == -1) cout << "IMPOSSIBLE" << endl;
    else cout << R << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}