[ 백준 16569 ] 화산 쇄설류 (C++)

백준의 화산쇄설류(16569) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 문제에서 구현해야 할 것이 몇가지 있기 때문에 어떻게 접근해야 하는지 부터 차근차근 알아가보도록 하자.

   문제를 간략하게 요약하면 이렇다. "화산이 곧 폭팔하는데, 폭팔하면 화산 쇄설류들이 주변 산들로 퍼져나간다.

   그런데 재상이는 화산 & 화산 쇄설류가 있는 곳으로는 갈 수가 없다. 이 때, 재상이가 갈 수 있는 가장 높은 곳은

   높이가 얼마이고 그 까지 가는데 몇 초가 걸리냐?" 이다.

   본인은 먼저 화산에 대한 계산을 모두 끝낸 후에 재상이를 움직여 주었다. 또한, 재상이가 움직일 때 화산의 상태를

   계속해서 비교해야 하기 때문에 화산에 대한 계산을 모두 진행하고, 그 결과값을 또 다른 2차원 맵을 하나 만들어서

   저장해 놓았다.

   여기서 말하는 결과값은 무엇일까?? 바로 화산이 퍼지는 시간이다. 쉽게 말하면 다음과 같은 맵을 만들었다는 것이다.

  

   위의 그림에 대해서 간략하게 설명해보자면, 현재 0초이고 가운데 빨강색으로 표시된 화산은 0초에서 폭팔한다.

   그리고 위의 검은색으로 표시된 화산은 10초에 폭팔한다고 가정해보면,

   왼쪽 맵의 상태를 오른쪽 맵으로 표현한 것이다. 오른쪽 맵에서 숫자는 화산 쇄설류가 흐르는 시간을 의미한다.

   이렇게, 화산쇄설류들이 퍼지는 시간을 따로 만들어서 저장해 주었다.

  

   위와 같이 화산에 대한 맵을 만들었다면, 이제 재상이를 움직여 주면 된다. 재상이가 움직일 때 신경써야할 것은 딱 2가지

   이다.

   1. 움직이려는 좌표가 화산인지 아닌지

   2. 움직이려는 좌표가 화산이 아니라면, 재상이가 움직이는 시간과 기존에 화산맵에 저장해둔 시간을 비교해서

     재상이가 움직일 수 있는 좌표인지 이렇게 2가지만 비교해주면 된다.

2) 그렇다면 구현에 대한 이야기로 넘어가겠다. 먼저 화산맵을 만들어보자.

   위에서 설명하지 않았지만, 정확하게 본인은 기존에 입력받는 맵 이외에 2개의 맵을 더 만들어 주었다.

   하나는 화산인지 아닌지를 체크해주는 맵(본문 : Volcano_MAP[][]),

   또 하나는 화산 쇄설류가 흐르는 시간을 저장해주는 맵(본문 : Volcano_Time[][])

   화산인지 아닌지를 체크해주는 맵은 정말 간단하다. 화산인 지점만 -1로 표현되어 있고 나머지 부분은 모두 0으로 표시되어

   있는 맵이다. 굳이 이렇게 맵을 2개를 만든 이유는 아래에서 설명하겠다.

   중요한건, 화산인지 아닌지를 체크해주는 Volcano_MAP이 아닌, Volcano_Time이다. 본인은 이 부분을 구현하기 위해서

   BFS탐색기법을 이용해서 시간을 비교하면서 구현해 주었다.

   이렇게 화산의 시간에 대한 맵을 모두 만들었다면 재상이를 움직여주면 된다. 재상이가 움직일 조건은 위에서 말했던

   2가지이다.

   그런데 위에서 말했던 2번 조건을 한번 봐보도록 하자. 기존의 화산시간맵에 저장해둔 시간을 비교해서 재상이가

   움직일 수 있는지 확인해 주어야 한다고 했다. 즉, (x, y)에 화산쇄설류가 2초에 덮치는데, 재상이가 (x, y)에 1초에

   갈 수 있다면 (x, y)는 재상이가 갈 수 있는 곳이다.

   그렇다면 화산이 있는 지점은 어떻게 판단해야할까?? 0 초로 설정하면 되지 않을까? 라고 생각해봤는데,

   본인이 Volcano_Time 맵을 만들 때, 화산이 폭팔하는 시간을 기준으로 탐색을 했기 때문에, 0초로 설정한다면

   이 시간들이 잘못 설정되었을 것이다. 이 부분 때문에 본인은 그냥 맵을 하나 더 만들었다.

   사실, 조건문 몇 개를 더 달아준다면 맵을 하나 더 만들지 않아도 될 것 같다...

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
 
#define endl "\n"
#define MAX 100
#define INF 987654321
using namespace std;
 
int N, M, V;
int Sx, Sy;
int MAP[MAX][MAX];
int Volcano_Time[MAX][MAX];
int Volcano_MAP[MAX][MAX];
bool Visit[MAX][MAX];
int Highest_Pos, Shortest_Time;
 
vector<pair<pair<int, int>, int>> Volcano_V;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Initialize()
{
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            Volcano_Time[i][j] = INF;
        }
    }
    Highest_Pos = Shortest_Time = 0;
}
 
void Print(int A[][MAX])
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (Volcano_MAP[i][j] == -1)
            {
                cout << "-1" << " ";
            }
            else
            {
                cout << A[i][j] << " ";
            }
        }
        cout << endl;
    }
}
 
void Input()
{
    cin >> N >> M >> V;
    cin >> Sx >> Sy;
    Sx = Sx - 1;
    Sy = Sy - 1;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
        }
    }
    for (int i = 0; i < V; i++)
    {
        int x, y, t;
        cin >> x >> y >> t;
        x = x - 1;
        y = y - 1;
        Volcano_MAP[x][y] = -1;
        Volcano_V.push_back(make_pair(make_pair(x, y), t));
    }
}
 
void Make_Volcano_MAP()
{
    for (int v = 0; v < Volcano_V.size(); v++)
    {
        memset(Visit, false, sizeof(Visit));
 
        int Volcano_X = Volcano_V[v].first.first;
        int Volcano_Y = Volcano_V[v].first.second;
        int Volcano_BT = Volcano_V[v].second;
 
        queue<pair<int, int>> Q;
        Q.push(make_pair(Volcano_X, Volcano_Y));
        Volcano_Time[Volcano_X][Volcano_Y] = Volcano_BT;
        
        int t = Volcano_BT + 1;
        while (Q.empty() == 0)
        {
            int Qs = Q.size();
            for (int s = 0; s < Qs; s++)
            {
                int x = Q.front().first;
                int y = Q.front().second;
                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 < N && ny < M)
                    {
                        if (Volcano_Time[nx][ny] > t)
                        {
                            Volcano_Time[nx][ny] = t;
                            Q.push(make_pair(nx, ny));
                        }
                    }
                }
            }
            t++;
        }
    }
}
 
void Move_Person()
{
    queue<pair<pair<int, int>, int>> Q;
    Q.push(make_pair(make_pair(Sx, Sy), 0));
    Visit[Sx][Sy] = 0;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int t = Q.front().second;
        Q.pop();
 
        if (MAP[x][y] > Highest_Pos)
        {
            Highest_Pos = MAP[x][y];
            Shortest_Time = t;
        }
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int nt = t + 1;
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)
            {
                if (Visit[nx][ny] == false)
                {
                    Visit[nx][ny] = true;
                    if (Volcano_MAP[nx][ny] == -1) continue;
                    if (Volcano_Time[nx][ny] > nt)
                    {
                        Q.push(make_pair(make_pair(nx, ny), nt));
                    }
                }
            }
        }
    }
}
 
void Solution()
{
    Make_Volcano_MAP();
    memset(Visit, false, sizeof(Visit));
    Move_Person();
}
 
void Solve()
{
    Initialize();
    Input();
    Solution();
    cout << Highest_Pos << " " << Shortest_Time << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}