[백준 15972번] [Dijkstra] 물탱크

Approach

문제를 잘 관찰해보면, 위에서 표현한 2차원 각 공간에 있을 수 있는 물의 높이는 다음과 같은 절차를 거쳐서 결정하게 된다.

 

1. 외부와 직접적으로 마주하고 있는 공간은 구멍의 높이에 맞춰서 무조건 높이가 형성이 된다.

2. 외부와 직접적으로 마주하고 있는 공간과 직접적으로 구멍이 뚫려있는 경우, 뚫린 구멍의 높이와 외부와 직접적으로 마주하고 있는 공간의 높이값 중 최댓값으로 결정된다. (잘 생각해보면 자명하다.)

3. 2의 과정을 반복함으로써 해당 영역에 위치한 물의 높이를 구할 수 있게 된다.

 

이때, 물이 계속해서 빠져나가는 상황이므로 넘치게 하는 최소 경계값을 구하는 것과 같고, 이는 다익스트라 문제로 회귀할 수 있게 된다. 최소값을 구해나간다는 점에서 dist를 업데이트하고 pq에서 뽑는 과정을 동일하게 활용할 수 있기 때문이다.

즉, dist를 해당 영역의 물의 높이로 잡고, 해당 값이 작아지는 방향으로 우선순위 큐에 넣고 update를 진행해주면 된다.

Code

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;

int move_x[4] = {-1, 1, 0, 0};
int move_y[4] = {0, 0, -1, 1};
vector<tiii> adj[1001][1001];
int dist[1001][1001];
const int INF = 2000000000;

int main() {
    fastio;
    int N, M, H;
    cin >> N >> M >> H;

    // 가로 방향으로 adj 연결
    for(int i = 0; i < N + 1; i++){
        int t;
        if(i == 0){
            for(int j = 1; j <= M; j++){ 
                cin >> t;
                if(t == -1) continue;
                adj[1][j].push_back({0, 0, t});
                adj[0][0].push_back({1, j, t});
            }
        }
        else if(i == N){
            for(int j = 1; j <= M; j++){
                cin >> t;
                if(t == -1) continue;
                adj[N][j].push_back({0, 0, t});
                adj[0][0].push_back({N, j, t});
            }
        }
        else{
            for(int j = 1; j <= M; j++){
                cin >> t;
                if(t == -1) continue;
                adj[i][j].push_back({i + 1, j, t});
                adj[i + 1][j].push_back({i, j, t});
            }
        }
    }

    for(int i = 1; i <= N; i++){
        for(int j = 0; j < M + 1; j++){
            int t;
            cin >> t;
            if(t == -1) continue;
            if(j == 0){
                adj[i][1].push_back({0, 0, t});
                adj[0][0].push_back({i, 1, t});
            }
            else if(j == M){
                adj[i][M].push_back({0, 0, t});
                adj[0][0].push_back({i, M, t});

            }
            else{
                adj[i][j].push_back({i, j + 1, t});
                adj[i][j + 1].push_back({i, j, t});
            }
        }
    }

    fill(&dist[0][0], &dist[1000][1001], INF);
    dist[0][0] = 0;
    priority_queue<tiii, vector<tiii>, greater<tiii> > pq;
    pq.push({0, 0, 0});
    while(!pq.empty()){
        int cur_cost, cur_x, cur_y;
        tie(cur_cost, cur_x, cur_y) = pq.top();
        pq.pop();
        if(dist[cur_x][cur_y] < cur_cost) continue;
        for(auto& p : adj[cur_x][cur_y]){
            int to_x, to_y, cost;
            tie(to_x, to_y, cost) = p;
            if(max(cur_cost, cost) < dist[to_x][to_y]){
                dist[to_x][to_y] = max(cur_cost, cost);
                pq.push({dist[to_x][to_y], to_x, to_y});
            }
        }
        if(cur_x == 0 && cur_y == 0){
            dist[0][0] = INF;
        }
    }

    int total = 0;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(dist[i][j] == INF) total += H;
            else total += dist[i][j];
        }
    }

    cout << total << "\n";
    return 0;   
}