(C++) 백준 1197번 - 최소 스패닝 트리

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

1197번: 최소 스패닝 트리

풀이

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

정렬 시에 가장 처음에 나타난 값을 기준으로 정렬하기에, cost 값을 튜플에 맨 앞에 위치시켜야 한다는 점을 간과하여 오랜 시간을 낭비하기도 했다. 

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

using namespace std;

int parent[100005];
tuple<int, int, int> t[100005];
int v, e, cost, x, y, result, cnt;

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 >> v >> e;
    for(int i = 0; i < e; i++){
        cin >> x >> y >> cost;
        t[i] = {cost, x, y};
    }
    sort(t, t+e);
    for(int i = 1; i <= v; 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 == v-1) break;
    }
    cout << result;
}