[BOJ / C++] 1197번 : 최소 스패닝 트리

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

Solved.ac 레벨

골드 IV

풀이

MST(Minimum Spanning Tree; 최소 신장 트리 or 최소 스패닝 트리)의 가중치를 구하는 문제다.

최소 신장 트리란 최소 간선의 개수로 모든 노드를 연결한 트리를 말한다.

최소 간선의 개수는 노드 개수 - 1개이며 모든 노드의 루트 노드는 1번 노드로 동일하다.

 

최소 신장 트리를 구할 수 있는 여러 방법 중에 크루스칼 알고리즘을 이용했다.

크루스칼 알고리즘을 이용하기 위해서는 합집합을 구하는 알고리즘, Union-Find 알고리즘에 대한 학습이 선행되어야 한다.

나는 아래 동빈나님의 두 영상을 통해 Union-Find 알고리즘과 크루스칼 알고리즘을 학습했고, 이 문제의 풀이 그 자체가 된다.

단순히 MST의 가중치를 구하는 문제이기 때문이다. 

 

Union-Find 알고리즘

크루스칼 알고리즘

 

Code

#include<bits/stdc++.h>

using namespace std;

int v, e, ans = 0;
int parent[10001];

//부모 노드 탐색
int getParent(int x) {
    if(parent[x] == x) return x;
    return parent[x] = getParent(parent[x]);
}

//두 부모 노드를 합치기
void unionParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);

    if(a < b) parent[b] = a;
    else parent[a] = b;
}

//같은 부모를 가지는지 확인
bool findParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);

    if(a == b) return true;
    else return false;
}



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

    cin >> v >> e;

    vector<pair<int, pair<int, int>>> MAP(e);

    for(int i = 0; i < e; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        MAP[i] = {c, {a, b}};
    }

    for(int i = 1; i <= v; i++) {
        parent[i] = i;
    }

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

    for(int i = 0; i < e; i++) {
        int start = MAP[i].second.first;
        int end = MAP[i].second.second;
        int cost = MAP[i].first;

        if(!findParent(start, end)) {
            ans += cost;
            unionParent(start, end);
        }
    }

    cout << ans << "\n";

    return 0;
}

1197번: 최소 스패닝 트리