(C++) 백준 1368번 - 물대기

문제 링크 : https://www.acmicpc.net/problem/1368

1368번: 물대기

풀이

새로운 우물을 파는 것은 새로운 정점을 하나 추가하여 그에 맞는 cost를 가지는 간선을 추가하는 방식으로 진행하였다.

Union-Find를 사용해서 크루스칼 알고리즘을 구현하여 최소 신장 트리의 크기를 구해보았다.

#include <iostream>
#include <algorithm>
#include <tuple>

using namespace std;

tuple<int, int, int> t[100005];
int n, e, cost, result, cnt;
int parent[305];

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

void uni(int x, int y){
    x = find(x);
    y = find(y);
    parent[y] = x;
}

bool is_diff_group(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return false;
    else return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> cost;
        t[e++] = {cost, i, n+1};
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> cost;
            if(i >= j) continue;
            t[e++] = {cost, i, j};
        }
    }
    n++;
    sort(t, t+e);
    for(int i = 1; i <= n; i++) parent[i] = i;
    for(int i = 0; i < e; i++){
        if(!is_diff_group(get<1>(t[i]), get<2>(t[i]))) continue;
        uni(get<1>(t[i]), get<2>(t[i]));
        result += get<0>(t[i]);
        cnt++;
        if(cnt == n-1) break;
    }
    cout << result;
}