백준/1197/MST/최소 스패닝 트리

백준/1197/MST/최소 스패닝 트리

MST 문제로 크루스칼 알고리즘을 사용하여 해결하였다.
우선 스패닝 트리(신장 트리)라하면 그래프의 부분 그래프들 중에서 모든 정점을 포함하는 트리를 의미한다.

1. 모든 정점을 포함해야한다.
2. 무방향 그래프여야한다.(사이클이 없어야한다.)
3. 주어진 정점이 V개 일때 간선의 개수는 V-1개 여야한다.

이러한 스패닝 트리중에서도 간선의 합이 최소가 되는 트리가 최소 스패닝 트리입니다.
이를 구하기 위해 크루스칼 알고리즘을 사용합니다.

1. 정점 u와 v는 서로 다른 집합이라 생각한다.
2. 정점 u와 v를 잇는 간선 중에 간선의 값이 최소가 되는 간선을 먼저 고른다.
3. 이어진 정점들은 서로 같은 집합으로 지정한다.
4. 이 후에 다시 최소가 되는 간선을 고르되 정점끼리 같은 집합에 속해 있다면 포함시키지 않는다.
5. 간선의 수가 정점의 수-1 일 때 알고리즘을 종료한다.

간단한 풀이라 생각하지마 u와 v를 같은 집합이라 구현해주는게 상당히 어렵다.
이를 위해 union-find 알고리즘을 사용한다.
union-find는 disjoint-set을 표시하기 위한 알고리즘 즉, 서로 다른 정점들이 같은 그래프에 속해 있는지를 확인하기 위한 알고리즘입니다.

1. 우선 각 정점을 자기 자신을 부모로 가진다.
2. 같은 집합의 정점임을 표시하기 위해 같은 부모로 표시한다.
   2-1. 부모를 정할 때는 최소 값(이는 다른 조건이 될 수도 있다.)이 다른 값의 부모가 된다.

int find(int num)
{
	if(a[num]==num)return num;
    return find(a[num]);
}
bool union(int u,int v)
{
	u=find(u); v=find(v);
    if(u==v)return 0;
    if(u<v) a[v]=u;
    else a[u]=v;
    return 1;
}
int main()
{
	int a[10];
    for(int i=0;i<10;i++)
    	a[i]=i;        
    union(a[0],a[1]);
}

union find를 이용해 서로 다른 집합으로 분류하기 이전 최소 값의 간선들을 먼저 정렬하고,
간선들을 하나씩 꺼내 정점들을 비교하면서 최소 스패닝 트리를 만들면된다.

#include<algorithm>
tuple<int,int,int> g[10005];
void solve()
{
	sort(g,g+E);
}

그러기 위해서 algorithm 헤더에 sort를 사용 tuple 자료구조는 맨 앞의 원소를 기준으로 정렬되기 때문에 맨 앞의 해당 간선의 값을 포함시킵니다.

void solve()
{
	int count=0;
	for(int i=0;i<E;i++)
    {
    	int cost,u,v;
        tie(cost,u,v)=g[i];
        if(!union(u,v))continue;
        result+=cost;
        count++;
        if(count==V-1)break;
    }
}

이 후 union_find가 false값이 나오면 서로 같은 그래프에 속해 있다는 뜻이니 continue 해주고 true 값이 나온다면 서로 다른 그래프에 속해 있다는 뜻이니 간선을 추가시킵니다.
이 때 count로 현재 추가된 간선의 개수를 저장하여 간선의 수가 정점의 수-1이 되면 해당 알고리즘을 종료합니다.

풀이

1. 첫번째 풀이

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

vector<int> p(10005,-1);
tuple<int,int,int>g[100005];

void solution();
void solve();

int V,E,result;

int getParent(int num)
{
    if(p[num]==-1)return num;
    return getParent(p[num]);
}

bool union_find(int u,int v)
{
    u=getParent(u); v=getParent(v);
    if(u==v)return 0;
    if(u<v)p[v]=u;
    else p[u]=v;
    return 1;
}

void solve()
{
    sort(g,g+E);
    int count=0;
    for(int i=0;i<E;i++)
    {
        int a,b,c;
        tie(a,b,c)=g[i];
        if(!union_find(b,c))continue;
        result+=a;
        count++;
        if(count==V-1)break;
    }    
    solution();
}

void solution()
{
    cout<<result;
}

int main()
{
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>V>>E;
    for(int i=0;i<E;i++)
    {
        int a,b,c;
        cin >> a>> b >>c;
        g[i]=tie(c,a,b);
    }
    
    solve();
}