[C/C++] 백준 #1922 네트워크 연결(크루스칼)

컴퓨터 네트워크를 공용망에 연결하지 않고, 체인 형태로 연결할 때, 최소 비용으로 모든 컴퓨터를 다 연결하고자 합니다.

 

컴퓨터간 연결하는 비용이 제시되었을 때, 이를 이용해서 가장 최소 비용으로 컴퓨터간 연결을 모두 합니다.

 

대표적인 최소 간선 비용 트리(MST : Minimum Spanning Tree) 문제입니다.

최소 간선 비용 트리를 만드는 방법은 여러가지가 있지만, 보편적으로 많이 사용되는 것이 크루스칼 알고리즘과 프림 알고리즘입니다.  그 외에도 몇가지 더 있죠.  집합 개념을 사용해서 집합갠 최소 비용 간선을 선택할 수도 있고요.  크루스칼 알고리즘과 같이 간선 가중치를 모두 정렬한 후에 최소 비용 간선을 선택하면서 집합을 늘려가는 방법도 있습니다.

 

제 경우에는 크루스칼 알고리즘을 이용했습니다.  여기서 배타적 집합(disjoint set)을 사용했는데, 축약을 이용하지는 않았습니다.  축약을 이용하는 경우 배타적 집합에서 검색비용이 \(O(1)\)이 되기 때문에 빠르게 진행할 수 있습니다.

 

제가 작성한 소스입니다.

//----------------------------------------------------------
//    baekjoon #1922
//        - by Aubrey Choi
//        - created at 2019-09-22
//----------------------------------------------------------
#include <stdio.h>
#include <algorithm>

struct Edge { int a, b, w; };
bool cmp(Edge &a, Edge &b) { return a.w < b.w; }
int main()
{
    int n, m, v[1000], sum=0;
    Edge e[100000];
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) v[i]=i;
    for(int i=0;i<m;i++)
        scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].w), e[i].a--,e[i].b--;
    std::sort(e,e+m,cmp);
    for(int i=0;n>1;i++)
    {
        int a=e[i].a, b=e[i].b;
        while(v[a]!=a) a=v[a];
        while(v[b]!=b) b=v[b];
        if(a==b) continue;
        v[b]=v[e[i].a]=v[e[i].b]=a; n--; sum+=e[i].w;
    }
    printf("%d\n", sum);
}

computer network