[백준 1197번] 최소 스패닝 트리

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

1197번: 최소 스패닝 트리

풀이) 

크루스칼 알고리즘을 이용하기 위해 간선 가중치를 기준으로 오름차순으로 정렬해주었고 이후 union-find 알고리즘을 사용하여 싸이클을 확인한 후 같은 집합이 아니라면 추가해주는 방식으로 해결하였다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int V, E, s, e, w, ans = 0;
int parent[10001];
pair<pair<int,int>, int> v[100001];

bool cmp(pair<pair<int,int>, int> v1, pair<pair<int,int>, int> v2){
    return v1.second < v2.second;
}

int getParent(int x)
{
    if(parent[x] == x)
        return (x);
    return getParent(parent[x]);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> V >> E;
    for(int i = 1; i <= V; i++)
        parent[i] = i;

    for(int i = 0; i < E; i++)
    {
        cin >> s >> e >> w;
        v[i].first.first = s;
        v[i].first.second = e;
        v[i].second = w;
    }
    sort(v, v + E, cmp);
    for(int i = 0; i < E; i++)
    {
        if (getParent(v[i].first.first) != getParent(v[i].first.second))
        {
            ans += v[i].second;
            s = getParent(v[i].first.first);
            e = getParent(v[i].first.second);
            if (s < e)
                parent[e] = s;
            else
                parent[s] = e;
        }
    }
    cout << ans;
    return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!