[1197번] 최소 스패닝 트리

문제 출처 :

https://www.acmicpc.net/problem/1197

알고리즘 분석 :

문제 해결에 필요한 사항

1. 유니온 파인드(Union Find) :: http://www.crocus.co.kr/683

2. 최소 스패닝 트리(MST) :: http://www.crocus.co.kr/733

이 문제는 최소 스패닝 트리 문제로 Kruskal Algorithm을 이용하면 해결 할 수 있다.

크루스칼 알고리즘은 유니온 파인드 방식과 상당히 유사한데,

간선의 정보만 오름차순으로 업데이트를 한번 해주면 그 이후로는 유니온 파인드 방식으로 해결 할 수 있다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
typedef struct kruskal {
    int from;
    int to;
    int val;
}KS;
 
vector<KS> edge;
 
int chk[10002];
int res;
 
bool comp(KS d1, KS d2)
{
    return d1.val < d2.val;
}
 
// 유니온 파인드의 파인드 방식
int find(int num)
{
    if (num == chk[num])
        return num;
 
    return chk[num] = find(chk[num]);
}
int main()
{
    int V, E;
 
    scanf("%d %d", &V, &E);
 
    for (int i = 1; i <= V; i++)
        chk[i] = i;
 
    // 그래프 형성
    for (int i = 0; i < E; i++)
    {
        KS ks;
        scanf("%d %d %d", &ks.from, &ks.to, &ks.val);
        edge.push_back(ks);
    }
 
    // 크루스칼 알고리즘에 의해 간선을 오름차순 정렬
    sort(edge.begin(), edge.end(), comp);
 
    // 유니온 파인드의 유니온 방식
    for (int i = 0; i < E; i++)
    {
        int nv = find(edge[i].from);
        int nw = find(edge[i].to);
 
        if (nv == nw)
            continue;
 
        chk[nv] = nw;
 
        res += edge[i].val;
    }
 
    printf("%d", res);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>