백준 - 1197 최소 스패닝 트리

문제 링크입니다 : https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

최소 스패닝 트리문제였다. 최소 스패닝 트리를 구현하는 방법은 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 있다.

 

프림 알고리즘은 시간 복잡도가 N^2이므로 이 문제는 접합하지 않은 것 같다. (시도해보지는 않았다.) 크루스칼 알고리즘의 시간복잡도는 NlogN이다. 그래서 크루스칼 알고리즘을 사용했고, 크루스칼 알고리즘은 모든 간선들에서 가장 비용이 낮은 비용들만 차례로 선택하면 되는 알고리즘이다. 이때, 선택하려는 간선이 이미 기존의 스패닝 트리의 일부분이라면 사이클이 생겨서 스패닝 트리가 아니게 된다. 그러므로 각 정점별로 집합 개념으로 나누어야한다. 이는 union-find로 해결했다.

 

그리고 스패닝 트리의 특징 중 하나는 V개의 정점을 선택하기 위해서 V - 1개의 간선을 선택해야 한다는 것이다. 그래서 간선의 개수를 V - 1개까지만 구하도록 크루스칼 알고리즘을 수행하면 된다.

 

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int, pair<int, int>>> adj;
vector<int> parents;
int V, E;

int findParent(int a) {
    if(a == parents[a]) return a;
    return parents[a] = findParent(parents[a]);
}

bool unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);
    if(a == b) return false;
    else if(a > b) parents[a] = b;
    else parents[b] = a;
    return true;
}

int main() {
    cin >> V >> E;
    parents.assign(V + 1, 0);
    for(int i = 0; i <= V; i++) {
        parents[i] = i;
    }

    int a, b ,c;
    for(int i = 0; i < E; i++) {
        cin >> a >> b >> c;
        // weight, u, v;
        adj.push_back({c, {a, b}});
    }

    sort(adj.begin(), adj.end());

    int cnt = 0;
    int sum = 0;
    for(int i = 0; cnt < V - 1 && i < adj.size(); i++) {
        if(unionParent(adj[i].second.first, adj[i].second.second)) {
            cnt++;
            sum += adj[i].first;
        }
    }

    cout << sum;

    return 0;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~