[백준 1197번] 최소 스패닝 트리

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

1197번: 최소 스패닝 트리

<문제 풀이>

 

Union-Find 알고리즘을 이용해서 기본적인 크루스칼 알고리즘을 구현하면 되는 문제입니다.

 

 

<C++ 소스 코드> 최소 스패닝 트리, 크루스칼 알고리즘

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
 
using namespace std;
 
pair<int, pair<int, int> > edge[100000];
 
int parents[10001];
 
 
int v, e;
 
int Find(int x){
    if(x == parents[x]) return x;
    else return parents[x] = Find(parents[x]);
}
 
 
void Union(int x, int y){
    int xParents = Find(x);
    int yParents = Find(y);
    parents[xParents] = yParents;
}
 
 
 
 
int solution(){
    int res = 0;
    int cnt = 0;
    sort(edge, edge + e);
    for(int i = 0 ; i < e; i++){
        int c = edge[i].first;
        int a = edge[i].second.first;
        int b = edge[i].second.second;
        if(Find(a) == Find(b)) continue; // 같은 그래프이면 무시
        Union(a, b); // a, b를 같은 그래프로 만듬
        res += c;
        cnt++;
        if(cnt == v - 1) break; // 최소 스패닝 트리를 만들면 종료
    }
    return res;
}
 
int main(void) {
    cin >> v >> e;
    for(int i = 1; i<=v; i++) parents[i] = i; // 처음엔 자기 자신이 부모
    for(int i = 0; i < e; i++){
        int a, b, c;
        cin >> a >> b >> c;
        edge[i].first = c;
        edge[i].second.first = a;
        edge[i].second.second = b;
    }
    
    cout<<solution();
    return 0;
}