문제

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


알고리즘

다익스트라


풀이

$N X M $ 격자판에 표면의 높이들이 주어질 때, 채울 수 있는 최대 물의 높이를 구하는 문제입니다.

격자판의 밖에서 격자판으로 물이 스며가는 형태로 구현을 했습니다. 즉 다익스트라의 시작점은 격자판의 테두리 부분이고 도착점은 테두리를 제외한 칸이라고 생각할 수 있습니다. 다익스트라는 하나의 시작점으로부터 하나의 도착지를 구하는 알고리즘이라 이를 적용하려면 약간의 테크닉을 써야합니다. A개의 시작점과 B개의 도착점이 주어졌다면, A개의 시작점들의 조상 시작점과 B개의 도착점들의 조상 도착점을 하나씩 만드는 것입니다. 아래코드에서는 각각 ij, ij+1로 사용하였습니다.

그리고 모든 격자판을 연결하는데, 높이가 높은 쪽에서 낮은쪽으로 가기 위해서는 높이 차이만큼 값을 지불하고 이동해야합니다. 이 값들을 $dist$배열에 저장하며 다익스트라를 종료한 시점에서는 해당 배열에 적힌 값이 곧 채울 수 있는 물의 높이들을 의미합니다.

다익스트라 그래프를 만드는 과정에서 음수의 간선이 발생하지만 이는 문제가 되지 않습니다. 다익스트라는 음수의 간선을 부정하는 것이 아닌 음수 사이클의 발생을 부정하기 때문입니다. 당연히 음수 사이클이 발생하지는 않습니다.

알고리즘은 굉장히 느린 편입니다…

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

typedef pair<int, int> pii;
const int dy[4] = { 1, -1, 0, 0 };
const int dx[4] = { 0, 0, 1, -1 };

int N, M;
int board[300][300];
int dist[90005];
vector<vector<pii>> adj;

bool inr(int y, int x) {
    return 0 <= y && y < N && 0 <= x && x < M;
}

long long dijkstra(int s) {
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    memset(dist, 0x3f, sizeof(dist));
    dist[s] = 0;
    pq.emplace(0, s);
    while (!pq.empty()) {
        auto [val, here] = pq.top();
        pq.pop();

        if (dist[here] < val)
            continue;

        for (auto [cost, there] : adj[here]) {
            if (dist[there] > val + cost) {
                dist[there] = val + cost;
                if (dist[there] < 0)
                    dist[there] = 0;
                pq.emplace(dist[there], there);
            }
        }
    }
    long long ans = 0;
    for (int i = 0; i < N * M; ++i) {
        ans += dist[i];
    }
    return ans;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> M >> N;
    adj.resize(N * M + 2);
    int start = N * M;
    int end = N * M + 1;
    rep(i, N) rep(j, M) {
        cin >> board[i][j];
    }
    rep(i, N) rep(j, M) {
        int here = i * M + j;
        rep(k, 4) {
            int ny = i + dy[k];
            int nx = j + dx[k];
            if (!inr(ny, nx))
                continue;
            adj[here].emplace_back(board[i][j] - board[ny][nx], ny * M + nx);
        }
        if (i == 0 || i == N - 1 || j == 0 || j == M - 1) {
            adj[start].emplace_back(0, here);
        } else {
            adj[here].emplace_back(0, end);
        }
    }

    cout << dijkstra(start);

    return 0;
}