[BOJ/Gold 4] 백준 16569 화산쇄설류(C++)

문제 링크

https://www.acmicpc.net/problem/16569

16569번: 화산쇄설류

 

 

문제

화산학자 윤재상은 어느 화산섬을 탐사하러 갔다가 곧 섬에 있는 화산들이 곧 폭발하기 시작할 것이라는 급보와 각 화산의 폭발 시점 정보를 받았다.

섬은 M행 N열의 행렬로 표현된다. 어떤 화산의 위치를 (x, y), 폭발을 시작한 시각을 t 라고 하자. t+δ 시각이 되면 δ ≥ |u-x|+|v-y|인 모든 (u, v)위치의 지대들은 높이 무관하게 화산쇄설류가 덮치게 된다. 재상인 빨리 탈출을 하고싶다.

• 재상이는 처음에 X행 Y열에 있다.
• 재상이는 단위 시간 당 상하좌우 한 칸만 움직일 수 있다.
• 재상이는 화산이 있는 위치와 화산쇄설류가 뒤덮인 곳은 갈 수 없다.

재상이는 화산쇄설류를 피해서 되도록 가장 높은 곳으로 피하고 싶고, 되도록 가장 빨리 도달하기를 원한다. 재상이가 화산쇄설류를 피해서 도달할 수 있는 가장 높은 고도와, 그 고도까지 도달하는데 걸리는 최소 시간을 구한다.

입력

첫 번째 줄에 정수 M, N, V이 공백으로 구분되어 주어진다. (1 ≤ M, N ≤ 100, 1 ≤ V ≤ min(5,000, M×N))

그 다음 줄에 X, Y가 공백으로 구분되어 주어진다. (1 ≤ X ≤ M, 1 ≤ Y ≤ N)

그 다음 줄부터 M개의 줄마다 N개의 공백으로 구분된 수들이 주어진다. i행 j열의 값은 (i, j) 지대의 고도 hij 를 나타낸다. (0 ≤ hij ≤ 10,000)

그 다음 줄부터 V개의 줄이 주어진다. i번째 줄에 xi, yi, ti가 공백으로 구분되어 주어진다. 이 수들은 i번째 화산의 위치 (xi, yi,)와 화산의 분출시각 ti를 의미한다. (1 ≤ xi ≤ M, 1 ≤ yi ≤ N, 0 ≤ ti ≤ 200)

위치, 시간, 고도 수치들은 모두 정수이다. X행 Y열에 화산이 있는 입력은 주어지지 않는다.

출력

재상이가 도달할 수 있는 최고 높이와 그 높이에 도달할 수 있는 최단 시간을 공백을 구분하여 출력한다.

예제 입력 1

8 8 8
5 8
58 34 30 23 12 44 18 30
4 62 26 42 64 39 44 25
64 34 6 10 0 25 46 34
42 3 62 48 20 25 25 41
35 30 4 33 35 39 41 38
7 43 37 3 0 25 20 23
20 59 18 43 1 14 16 11
17 50 12 19 59 48 7 4
4 5 4
2 6 4
5 1 2
8 8 3
5 6 2
8 2 2
5 2 1
3 5 2

예제 출력 1

46 3

예제 입력 2

8 8 8
1 8
7 9 1 60 5 49 19 27
38 25 18 1 52 43 22 0
20 35 39 43 10 17 34 43
21 50 13 34 64 57 24 48
64 18 14 40 62 11 3 58
64 22 60 15 5 16 59 8
1 61 19 9 13 53 50 14
5 30 7 13 44 25 15 63
2 3 2
2 7 2
4 6 2
2 8 2
5 8 2
4 7 2
5 2 5
6 3 1

예제 출력 2

49 2

알고리즘 분류

• 구현
• 그래프 탐색

풀이

먼저 V개의 화산이 특정 시점에 폭발해서 화산쇄설류가 각 칸에 언제 퍼지는지를 BFS를 통해서 확인한다.

화산의 좌표와 시간을 담을 큐와 특정 칸으로 이동이 불가능해지는 시점을 기록하는 2차원 배열을 선언한다.

먼저 V개의 화산은 폭발하는 시점부터 방문할 수 없다고 하자. 그리고 좌표와 폭발 시각을 큐에 push한다.

그리고 BFS를 수행하면서, 특정 시점에 언제 화산쇄설류가 퍼지는 지 최소의 시간을 기록한다.

화산은 애초에 방문할 수 없기 때문에 원래는 2차원 배열에서 화산의 방문 불가 시각은 0이어야 하지만, 처음부터 0으로 기록해버리면 BFS를 수행할 때 화산쇄설류가 다른 화산이 있는 칸으로 퍼질 수 없기 때문에 화산이 폭발하는 시점부터 방문할 수 없다고 일단 기록해두었다.

BFS를 수행하여 화산쇄설류가 각 칸에 퍼지는 최소의 시각을 기록했다면, V개의 화산이 존재하는 각각의 칸의 방문 불가 시점을 다시 0으로 초기화한다.

그리고 재상이의 초기 위치부터 BFS를 수행하여, 각 칸의 방문 불가 시각보다 먼저 재상이가 도달할 수 있고, 그 칸 중에서 높이가 가장 높은 칸과, 그 칸까지 도달하기 위해 걸리는 최소의 시각을 구하고 공백으로 구분해서 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 201
#define INF 1e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int M, N, V, Y, X;
int H[MAX][MAX];
int Banned[MAX][MAX];
bool Visited[MAX][MAX];
int MoveY[4] = { -1,0,1,0 };
int MoveX[4] = { 0,-1,0,1 };
queue<pair<pair<int, int>, int> > Volcano;
vector<pair<int, int> > Vec;
int AnswerH, AnswerT;

void init() {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            Banned[i][j] = INF;
        }
    }
}

void input() {
    cin >> M >> N >> V;
    cin >> Y >> X;
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> H[i][j];
        }
    }
    for (int i = 0; i < V; i++) {
        int A, B, C;
        cin >> A >> B >> C;
        Banned[A][B] = C;
        Volcano.push(make_pair(make_pair(A, B), C));
        Vec.push_back(make_pair(A, B));
    }
}

void BFS1() {
    while (!Volcano.empty()) {
        int NowY = Volcano.front().first.first;
        int NowX = Volcano.front().first.second;
        int NowT = Volcano.front().second;
        Volcano.pop();

        for (int i = 0; i < 4; i++) {
            int NextY = NowY + MoveY[i];
            int NextX = NowX + MoveX[i];
            if ((NextY >= 1) && (NextY <= M) && (NextX >= 1) && (NextX <= N)) {
                if (Banned[NextY][NextX] > NowT + 1) {
                    Banned[NextY][NextX] = NowT + 1;
                    Volcano.push(make_pair(make_pair(NextY, NextX), NowT + 1));
                }
            }
        }
    };
}

void BFS2() {
    queue<pair<pair<int, int>, int> > Q;
    Visited[Y][X] = true;
    AnswerH = H[Y][X];
    AnswerT = 0;
    Q.push(make_pair(make_pair(Y, X), 0));

    while (!Q.empty()) {
        int NowY = Q.front().first.first;
        int NowX = Q.front().first.second;
        int NowT = Q.front().second;
        Q.pop();

        if (AnswerH < H[NowY][NowX]) {
            AnswerH = H[NowY][NowX];
            AnswerT = NowT;
        }
        else if (AnswerH == H[NowY][NowX]) {
            AnswerT = min(AnswerT, NowT);
        }

        for (int i = 0; i < 4; i++) {
            int NextY = NowY + MoveY[i];
            int NextX = NowX + MoveX[i];
            if ((NextY >= 1) && (NextY <= M) && (NextX >= 1) && (NextX <= N)) {
                if (Banned[NextY][NextX] == INF) {
                    if (!Visited[NextY][NextX]) {
                        Visited[NextY][NextX] = true;
                        Q.push(make_pair(make_pair(NextY, NextX), NowT + 1));
                    }
                }
                else {
                    if (Banned[NextY][NextX] > NowT + 1) {
                        if (!Visited[NextY][NextX]) {
                            Visited[NextY][NextX] = true;
                            Q.push(make_pair(make_pair(NextY, NextX), NowT + 1));
                        }
                    }
                }
            }
        }
    };
}

void settings() {
    BFS1();
    for (int i = 0; i < V; i++) {
        Banned[Vec[i].first][Vec[i].second] = 0;
    }
    BFS2();
}

void find_Answer() {
    cout << AnswerH << " " << AnswerT << "\n";
}

int main() {
    FASTIO
    init();
    input();
    settings();
    find_Answer();

    return 0;
}