78. 원더랜드 [Kruskal MST 알고리즘]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개

 

풀이 

- 크루스칼 알고리즘: 최소신장트리를 구성하는 알고리즘으로 k개의 노드에 K-1개의 간선을 선택한다.

- 가장 적은 비용으로 트리를 구성하는데 가중치를 오름차순 정렬한 후 가중치가 낮은 간선을 먼저 선택한다.

- for문을 돌면서 v1, v2의 집합이 같은지 find로 확인 후 같지 않으면 res에 가중치를 더하고 두 집합을 하나로 union한다.

- union : find로 a,b의 집합을 찾고 이 집합이 서로 다를시에 unf[a]=b함으로써 하나로 합쳐준다.

- 앞서 푼 문제와 union&find로 같은 알고리즘을 사용한다

 

 

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int unf[10001];

//78. 원더랜드(Kruskal MST 알고리즘)
//최소비용 트리

struct Edge{
    int v1;
    int v2;
    int val;
    Edge(int a, int b, int c){
        v1=a;
        v2=b;
        val=c;
    }
    bool operator<(const Edge &b) const{
        return val<b.val;
    }
};

int Find(int v){
    if(v==unf[v]) return v;
    else return unf[v]=Find(unf[v]);
}

void Union(int a, int b){
    a=Find(a);
    b=Find(b);
    if(a!=b) unf[a]=b;
}

int main(){
    vector<Edge> Ed;
    int i, n, m, a, b, c, res=0;
    scanf("%d %d", &n, &m);
    for(i=1;i<=n;i++){
        unf[i]=i;
    }
    for(i=1;i<=m;i++){
        scanf("%d %d %d", &a, &b, &c);
        Ed.push_back(Edge(a, b, c));
    }
    sort(Ed.begin(), Ed.end()); //가중치 오름차순 정렬
    for(i=0;i<m;i++){
        //두개 정점 Find
        int fa=Find(Ed[i].v1);
        int fb=Find(Ed[i].v2);
        if(fa!=fb){
            //다른 집합이면 가중치를 더하고
            res+=Ed[i].val;
            //Union한다
            Union(Ed[i].v1, Ed[i].v2);
        }
    }
    printf("%d\n", res);
    return 0;
}