MST (Minimum Spanning Tree) 최소 신장 트리

MST 즉 최소신장트리 (최소 스패닝 트리)는 간선에 weight가 있는 그래프를 tree로 만들어 문제를 해결할때 유용하게 사용할 수 있다.

그래프를 최소 비용 간선을 가진 tree로 만드는 방법을 MST 라고 한다.

 

MST를 만들 조건은

1. 그래프 간선에 weight가 있을 경우

2. Cycle이 없어야 할 경우

라고 할 수 있다.

 

MST는 kruskal 알고리즘을 사용하여 tree를 구성하는데, 아래와 같이 동작한다.

 

1. 가장 weight가 적은 간선을 선택

2. 선택된 간선에 연결된 두 노드가 같은 tree인지 확인한다.

3-1. 두 노드가 서로 다른 tree인 경우 같은 tree로 만들고 1로 돌아간다.

3-1. 두 노드가 같은 tree인 경우 1로 돌아간다.

이것을 반복할 경우, weight가 가장 적은 간선을 바탕으로 노드를 tree 형태로 구성할 수 있다.

 

아래 예시를 통해 tree를 구성해보자.

처음에 모든 노드는 각각 다른 그래프에 포함된다고 가정한다.

가장 weight가 적은 간선은 3의 weight를 가진 간선이다.

이 가선에 연결된 노드는 2,4 노드이고, 각각 다른 그래프이므로, 두 노드를 한 그래프로 만들어준다.

다음으로 간선의 weight가 작은 간선은 4를 가진 간선이고, 노드 1,4가 연결 되어있다.

노드 1,4는 서로 다른 그래프에 포함되어있으므로, 같은 그래프로 만들어준다.

 

이런 식으로 반복할 경우, 간선의 weight가 가장 적은 그래프를 생성할 수 있다.

 

이제 구현상의 문제를 생각해보면

1. 어떻게 두 노드가 같은 그래프인지 아닌지 판단할 것인가.

2. 어떻게 두 노드를 한 그래프로 묶을 것인가

를 해결해야 하는데, 이를 해결하기 위해 Union-find 또는 disjoint-set 이라는 알고리즘을 사용한다.

 

한 tree를 구성할때 번호가 작은 노드가 번호가 큰 노드의 부모라고 가정할 때, 각 노드의 가장 부모를 root로 정의한다.

이렇게 구성할 경우, 한 그래프에 포함 되는 모든 노드는 같은 root를 가지고 있고, root를 비교하므로써 같은 그래프에 포함 되는지 아닌지를 판단 할 수 있다.

 

한 그래프로 묶는 것 또한 두 노드의 root를 같게 저장하면, 한 그래프로 묶을 수 있다.

 

<소스코드>

#include<iostream>
#include<string>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<bitset>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
struct edge{
    int a;
    int b;
    int c;
};
 
int n,m;
vector<edge> v;
 
bool operator < (edge a, edge b){ // 우리가 만든 struct를 사용하는 템플릿에 대해 대소 비교를 하기 위해서 오버로딩
    if(a.c < b.c){
        return true;
    }
    else{
        return false;
    }
}
 
int parent[100001]; // 대장 내 노드의 대장을 저장함.
// parent[2] = 1 , Parent[3] = 1 이면 노드 1,2,3은 같은 그래프
 
int get_pa(int x){
    if(parent[x] == x){ // 내가 대장
        return x;
    }
    else{ // 내가 대장이 아닐 경우 재귀 돌아서 대장을 찾을때 까지 가서 대장을 찾음.
        parent[x] = get_pa(parent[x]); // 이렇게 안할 경우 같은 그래프임에도 대장이 다를 수 있음. 중요한 부분.
        // 재귀로 여기서 덮어 씌워놔야 다른 곳에서 재귀를 계속 안돌고 적은 시간내에 덮어쓴 값을 바탕으로 빠르게 대장 을 알 수 있음
        return parent[x];
        
        // return get_pa(parent[x]);
        // 이렇게 할 경우 시간초과가 남.
    }
}
 
void Union(int a, int b){ // 대장을 작은 놈으로 바꿔줘서 가은 그래프로 보이게 함
    
    if(a<b){
        parent[b] = a;
    }
    else{
        parent[a] = b;
    }
}
 
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin>>n>>m;
    
    for(int i = 1; i<=n; i++){
        parent[i] = i;
    }
    
    for(int i = 0; i<m; i++){
        int a,b,c;
        cin>>a>>b>>c;
        edge e;
        e.a = a;
        e.b = b;
        e.c = c;
        v.push_back(e);
    }
    
    sort(v.begin(), v.end());
    
    int ans = 0;
    int las = 0;
    for(int i = 0; i<m; i++){
        int a,b,c;
        a = v[i].a;
        b = v[i].b;
        c = v[i].c;
        
        int ap = get_pa(a);
        int bp = get_pa(b);
        if(ap!=bp){ //a와 b가 같은 그래프가 아니면
            ans+=c;
            Union(ap,bp); // 하나의 그래프로 합쳐줌
        }
    }
    
    cout<<ans<<endl;
}