백준 1197 최소 스패닝 트리 - C++, 크루스칼 알고리즘

 

1197번: 최소 스패닝 트리

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int v, e, res = 0, edgenum = 0;
pair<int, pair<int , int>> edge[100001];
int parents[10001];

int FindRoot(int x){
    if(x == parents[x])
        return x;
    return parents[x] = FindRoot(parents[x]);
}

void Merge(int x, int y){
    x = FindRoot(x);
    y = FindRoot(y);

    if(x == y)
        return;
    parents[x] = y;
}

int main(){
    scanf("%d %d", &v, &e);
    
    for(int i = 0; i <= v; i++)
        parents[i] = i;

    for(int i = 0; i < e; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        edge[i].first = c;
        edge[i].second.first = a;
        edge[i].second.second = b;
    }

    sort(edge, edge + e);
    
    // 간선 갯수만큼 크루스칼 알고리즘
    for(int i = 0; i < e; i++){
        if(FindRoot(edge[i].second.first) == FindRoot(edge[i].second.second))
            continue;
        
        Merge(edge[i].second.first, edge[i].second.second);
        res += edge[i].first;
        edgenum++;
        if(edgenum == v - 1)
            break;
    }
    printf("%d\n", res);
}

---

 이전에 Union Find를 공부한 뒤 풀이할려고 둘 문제인데 다른 일을 많이 한다고 알고리즘을 못풀다가 이제야 풀이를 한다. 이전의 Union Find에서 크루스칼 알고리즘을 적용한 것으로 최소 스패닝 트리를 구하기 위해서 간선들을 정렬해준 뒤 작은 것들부터, 부모를 합쳐가면서 최소 스패닝 트리를 만드는데 이때 '부모가 같다 = 사이클이 있다' 이므로 이 경우를 제외하고 크루스칼 알고리즘을 진행하면 답이 나온다.