[Algorithm] 1197: MST

• toc {:toc}

📦1197: MST

---

[알고리즘 풀이] 강동규
Reviewed by Kade Kang (devkade12@gmail.com)
Reviewed:: 2024-02-18
문제 확인하기

풀이

• Union Find 방법을 사용했다.
• 최솟값을 알고 싶은 것이기 때문에 가중치가 가장 적은 순서대로 나열한다.
• 시작점과 끝점의 부모를 찾아 비교하고, 부모가 서로 다르면(서로 연결되어 있지 않다면) 연결한다.
• 이를 모든 간선에 대해 확인하면 최소 스패닝 트리가 만들어진다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#define endl '\n'
using namespace std;
 
int V, E, A, B, C;
int parent[10001];
int res = 0;
vector<tuple<int, int, int>> graph;
 
int Find(int x){
    if (parent[x] == x) return x;
    else return parent[x] = Find(parent[x]);
}
 
int Union(int i){
    int x = get<1>(graph[i]);
    int y = get<2>(graph[i]);
    x = Find(x);
    y = Find(y);
    if(x != y){
        parent[y] = x;
        return get<0>(graph[i]);
    }
    return 0;
}
 
void Initialize(){
    for(int i=1; i<=V; i++){
        parent[i] = i;
    }
}
 
void Input(){
    cin >> V >> E;
    for(int i=0; i<E; i++){
        cin >> A >> B >> C;
        graph.push_back(make_tuple(C, A, B));
    }
    sort(graph.begin(), graph.end());
}
 
void Solution(){
    for(int i=0; i<E; i++){
        res += Union(i);
    }
    cout << res << endl;
}
 
int main(){
   ios::sync_with_stdio(0);
    cin.tie(0);
 
    Input();
    Initialize();
    Solution();
 
    return 0;
}