[C/C++] 백준 #1647 도시 분할 계획(크루스칼 알고리즘)

이번 문제는 전형적인 최소 스패닝 트리(Minimum Spanning Tree) 문제입니다.

 

최소 스패닝 트리를 구하는 방법중 대표적인 방법은 프림(Prim) 알고리즘과 크루스칼(Kruskal) 알고리즘이 있습니다.

둘 중에 어떤 알고리즘이 좋은가를 할 때에는 제 개인적으로는 크루스칼 알고리즘이 더 좋습니다.

 

알고리즘 효율은 프림 알고리즘은 \(O(E \log E)\)이고 크루스칼 알고리즘은 \(O(E \log E)\) 로 비슷합니다.  물론 우선순위큐를 잘 만들면 프림 알고리즘은 \(O(E \log V)\) 까지도 가능하지만, 사실상 의미가 없습니다.  \(E\) 자체의 최대치가 \(V(V-1)/2\) 이므로 로그(log) 함수 안에서는 아무런 의미가 없습니다.

 

개인적으로 크루스칼 알고리즘을 더 선호하는 이유는 정렬 알고리즘을 사용하기 때문입니다.  우선순위큐를 잘 만들더라도 정렬 알고리즘의 효율을 따라가기 힘들죠.   그래서 가능하면 크루스칼 알고리즘으로 푸는 것이 더 좋을 듯 합니다.

 

크루스칼 알고리즘을 이용하려면 우선순위큐는 사용되지 않지만, 배타적 집합(disjoint set) 알고리즘을 적용해야 합니다.  프림 알고리즘에서 방문 기록을 남기는 것이나 배타적 집합을 사용하는 것이나 크게 다르지 않습니다.

 

 

제가 작성한 소스입니다.  배타적 집합에서 축약을 구현하지 않았네요.  축약을 구현하는 것과 아닌 것은 속도면에서 차이가 많습니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------------------------------------
//    baekjoon #1647 - City Division Plan.
//        - by Aubrey Choi
//        - created at 2019-08-07
//----------------------------------------------------------------------------------------
#include <stdio.h>
#include <algorithm>

struct Edge { int a, b, c; };
Edge e[1000000];
int v[100001];
bool cmp(const Edge &a, const Edge &b) { return a.c < b.c; }
int main()
{
    int n, m, cnt=2, ans=0;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++) scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
    std::sort(e,e+m,cmp);
    for(int i=0;cnt<n;i++)
    {
        int g1=e[i].a, g2=e[i].b;
        while(v[g1]) g1=v[g1];
        while(v[g2]) g2=v[g2];
        if(g1==g2) continue;
        v[g2]=v[e[i].b]=g1; if(e[i].a!=g1) v[e[i].a]=g1;
        ans+=e[i].c, cnt++;
    }
    printf("%d\n", ans);
}