[백준] 1368 물대기

문제 링크

http://icpc.me/1368

1368번: 물대기

풀이

MST를 이용하여 풀 수 있다.

가상의 루트 노드를 하나 만들고, 어떤 물을 킬 때, 루트 노드에서 물을 끌어온다고 생각하면 쉽게 풀 수 있다.

물은 키는 행위는 루트 노드와 킬 노드를 연결시키는 것으로 매핑시키면 된다.

코드

#include <bits/stdc++.h>
using namespace std;

struct T { int x, y, z; };
vector<T> arr;

int mat[302][302];
int par[302];

int find(int x) {
    if (x == par[x]) return x;
    return par[x] = find(par[x]);
}

void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    par[y] = x;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        int inp; cin >> inp;
        arr.push_back({i, 0, inp});
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> mat[i][j];
            if (i != j) arr.push_back({i, j, mat[i][j]});
        }
    }
    for (int i = 0; i <= n; i++) par[i] = i;
    sort(arr.begin(), arr.end(), [](T a, T b) { return a.z < b.z; });
    int ans = 0;
    for (auto [x, y, cost]: arr) {
        x = find(x), y = find(y);
        if (x != y) {
            merge(x, y);
            ans += cost;
        }
    }
    printf("%d", ans);
}