[BOJ] 백준 1197 최소 스패닝 트리 c++ (크루스칼)

문제 출처 : https://www.acmicpc.net/problem/1197 

1197번: 최소 스패닝 트리

---

최소 스패닝 트리(최소 신장 트리)

우선 스패닝 트리는 그래프의 모든 정점을 잇고, 사이클이 없는 트리이다.

• 정점이 V개면 정점을 연결하는 간선은 V-1개이다.

최소 스패닝 트리는 간선의 가중치 합이 최소가 되는 스패닝 트리이다.

 

최소 스패닝 트리를 구하는 대표적인 알고리즘은 크루스칼(Kruskal), 프림(Prim) 알고리즘이 있다.

이번에는 크루스칼 알고리즘으로 풀이하였다.

---

크루스칼 알고리즘

크루스칼 알고리즘은 기준 간선을 중심으로 그리디 알고리즘을 통해 최소 스패닝 트리를 구하는 알고리즘이다.

1. 선택하지 않은 간선 중 최소 가중치인 간선을 선택
2. 간선을 선택했을때, 사이클이 없는 경우 선택 확정
3. 모든 정점을 연결하는 간선(V-1개)을 선택할때까지 반복

사이클은 어떻게 판단할까? 바로 유니온 파인드를 통해 판단할 수 있다.

선택한 간선과 기준 간선의 최상위 Parent가 같다면 사이클이 발생한다.

유니온 파인드 관련 설명은 아래 참고

https://0m1n.tistory.com/74

[BOJ] 백준 16562 친구비 c++ (유니온 파인드)

 

---

풀이

1. 선택하지 않은 간선 중 최소 가중치인 간선을 선택

• 입력을 받은 후 sort를 통해 가중치 오름차순으로 정렬한다.
• 유니온 파인드 parent 배열 초기화를 진행한다.

cin >> V >> E;
for(int i = 0; i < E; i++){
    int a, b, c;
    cin >> a >> b >> c;
    v.push_back({c, {a, b}});
}
sort(v.begin(), v.end());
for(int i = 1; i <= V; i++)
    parent[i] = i;

2. 간선을 선택했을때, 사이클이 없는 경우 선택 확정

3. 모든 정점을 연결하는 간선(V-1개)을 선택할때까지 반복

• findParent()를 통해 부모가 같은 경우, 사이클이므로 pass한다.
• 그 후, 선택한 간선을 확정하므로 기준 간선과 선택 간선을 unionParent 함수에 넘겨준다.
• 정답은 가중치를 출력하라고 했으므로 cost를 더해주면 된다.

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

void unionParent(int a, int b){
    a = findParent(a);
    b = findParent(b);
    parent[b] = a;
}

.....

int cnt = 0;
for(int i = 0; i < v.size(); i++){
    T curEdge = v[i];
    int cost = curEdge.first;
    int now = curEdge.second.first;
    int next = curEdge.second.second;

    if(findParent(now) == findParent(next)) continue; // 사이클이면 pass

    unionParent(now, next);
    ans += cost;

    if(++cnt == V - 1) break;
}

---

코드

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

using namespace std;
typedef pair<int, pair<int, int>> T;

int V, E;
vector<T> v;
int parent[10000+1];
int ans;

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

void unionParent(int a, int b){
    a = findParent(a);
    b = findParent(b);
    parent[b] = a;
}

int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> V >> E;
    for(int i = 0; i < E; i++){
        int a, b, c;
        cin >> a >> b >> c;
        v.push_back({c, {a, b}});
    }
    sort(v.begin(), v.end());
    for(int i = 1; i <= V; i++)
        parent[i] = i;

    int cnt = 0;
    for(int i = 0; i < v.size(); i++){
        T curEdge = v[i];
        int cost = curEdge.first;
        int now = curEdge.second.first;
        int next = curEdge.second.second;

        if(findParent(now) == findParent(next)) continue; // 사이클이면 pass

        unionParent(now, next);
        ans += cost;

        if(++cnt == V - 1) break;
    }
    cout << ans << '\n';
    return 0;
}