[백준] 1197 최소 스패닝 트리 (C++)

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

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보다 작거나 같은 데이터만 입력으로 주어진다.

출력

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

---

풀이

최소 스패닝 트리 (MST) 문제이다.

위 문제를 푸는 대표적인 방법으로는 크루스칼 알고리즘과 프림 알고리즘이 있는데,

크루스칼 알고리즘을 사용하여 문제를 풀었다.

크루스칼 알고리즘

크루스칼 알고리즘의 아이디어는 다음과 같다.

1. 주어진 간선들을 가중치 기준으로 내림차순으로 정렬한다.

2. 비용이 가장 작은 간선을 선택한다.

3. 간선을 선택하였을 때 사이클(순환)이 발생하지 않는다면 해당 간선의 가중치를 더한다.

4. 모든 노드를 방문할 때 까지 2, 3을 반복한다.

 

그림을 통한 예시는 다음과 같다.

 위와 같이 정점(V)이 4개, 간선(E)이 5개 있고 간선들을 가중치 기준 내림차순으로 정렬하였다.

첫 번째 간선을 골라 연결한다.

 

두 번째 간선을 골라 연결한다.

 

세 번째 간선을 골라 연결한다. 이 때 사이클(순환)이 발생하므로 세 번째 간선의 가중치는 추가하지 않는다.

 

네 번째 간선을 골라 연결한다. 이 때 모든 정점을 방문하였으므로 종료한다.

 

여기서 사이클이 발생하는지를 확인하는 방법으로는 분리 집합(Union-Find)을 사용한다.

 

처음에 간선을 선택하였을 때 시작점과 도착점의 부모(Find 연산)가 같다면 사이클이 발생하는 것이고

부모가 다르다면 사이클이 발생하지 않는다.

 

만약 사이클이 발생하지 않는다면 가중치를 더해주고 시작점과 도착점에 대해 Union을 진행하면 된다.

 

코드

#include <iostream>
#include <queue>
using namespace std;

int v, e;
// 우선순위 큐를 이용하여 간선의 가중치순대로 정렬
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
int root[10001];

// find 함수 구현
int Find(int x){
    if (x == root[x]){
        return x;
    }
    return root[x] = Find(root[x]);
}

// union 함수 구현
void Union(int x, int y){
    x = Find(x);
    y = Find(y);
    root[y] = x;
}

void solve(){
    // root 기본값 설정
    for (int i = 1; i < v; i++){
        root[i] = i;
    }

    int visitedNode = 1;
    long long answer = 0;

    // 간선을 모두 방문한다면 while문 탈출
    // 만약 모든 노드가 연결되지 않을 수 있다는 조건이 있다면 !pq.empty()를 추가하면 된다.
    while (visitedNode < v){
        int distance = pq.top().first;
        int start = pq.top().second.first;
        int finish = pq.top().second.second;
        pq.pop();
        
        // 사이클이 발생하지 않는다면
        if (Find(start) != Find(finish)){
            Union(start, finish);
            answer += distance;
            visitedNode++;
        }
    }

    cout << answer;
}

int main(){
    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;

        pq.push({c,{a,b}});
    }

    solve();
}