[백준] 최소 스패닝 트리

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

1197번: 최소 스패닝 트리

우선 문제부터 간단하게 요약하면,

 

문제 제목에서 의미하는 것과 같이, 최소 신장 트리의 cost를 return 해야 하는 문제입니다.

 

<Solution>

최소 신장 트리는 Kruskal 알고리즘이나 Prim알고리즘을 사용한다고 합니다. 

 

Prim 알고리즘의 경우 아직 한번도 구현해 본적이 없어서 예전에 파이썬으로 구현해본 Kruskal알고리즘으로 구현하였습니다. 

 

실제 구현은 아래와 같습니다. 

#include <iostream>
#include <algorithm>

using namespace std;

struct edge{
    int s;
    int d;
    int cost;
};

edge edges[100000+10];

int parent[10000+10];

int V, E;
int ans;

bool Compare(const edge &e1, const edge &e2){
    return e1.cost < e2.cost;
}

int findParent(int v){
    if(parent[v] != v){
        parent[v] = findParent(parent[v]);
    }
    return parent[v];
}

void unionSet(int v1, int v2){
    int p1 = findParent(v1);
    int p2 = findParent(v2);
    
    if(p1 > p2){
        parent[p1] = p2;
    }
    else{
        parent[p2] = p1;
    }
}

int main(){
    // get input 
    cin >> V >> E;

    for(int i = 0; i<E; i++){
        cin >> edges[i].s >> edges[i].d >> edges[i].cost;
    }

    // initialize parent array
    for(int i = 1; i<=V; i++){
        parent[i] = i;
    }

    // sort edges
    sort(edges, edges+E, Compare);

    // looking for each edges, do Kruskal MST algorithm
    for(int i = 0; i<E; i++){
        edge* cur_e = edges+i;
        // if it doesn't make cycle, insert it in set
        if(findParent(cur_e->s) != findParent(cur_e->d)){
            unionSet(cur_e->s, cur_e->d);
            ans += cur_e->cost;
        }

    }

    cout << ans << endl;
}