[C++] 백준 1647번: 도시 분할 계획 (최소 신장 트리)

https://www.acmicpc.net/problem/1647

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

한 마을을 두 마을로 분리할 때, 두 마을을 유지하는 길의 최소 비용을 구하여라.

---

시간복잡도 어림하기

 최소 신장 트리(Minimum Spanning Tree)

 그래프의 모든 노드를 최소 비용으로 연결해야 하는 문제이므로 최소 신장 트리를 만드는 문제입니다. 최소 신장 트리는 크루스칼(Kruskal), 프림(Prim) 알고리즘으로 찾을 수 있습니다.

 크루스칼 알고리즘은 간선 선택 기반 최소 신장 트리 구성 알고리즘으로 O(eloge)의 시간복잡도를 가지고, 프림 알고리즘은 정점 선택 기반 알고리즘으로 O(n^2)의 시간복잡도를 가집니다. 문제에서 e의 최댓값은 1,000,000이고 n의 최댓값은 100,000 입니다. n^2은 100,000 x 100,000 = 10,000,000,000(백억)으로 제한 시간내에 풀기 어려운 수치입니다. 따라서 크루스칼 알고리즘을 사용해야 합니다.

---

알고리즘 설계하기

 크루스칼 알고리즘의 로직은 다음과 같습니다.

1. 그래프 내의 모든 간선을 오름차순으로 정리한다.
2. 선택되지 않은 간선을 대상으로 가장 작은 가중치를 가지는 간선을 선택한다.
3. 선택한 간선이 사이클을 형성하지 않는다면 최소 신장 트리에 추가한다.
4. 선택한 간선이 사이클을 형성한다면 무시한다.
5. 2번으로 돌아가 모든 간선이 선택될 때까지 반복한다.

 이와 같이 크루스칼 알고리즘을 실행하면 마을의 모든 노드를 최소 비용으로 연결할 수 있습니다.

 위 로직의 핵심은 선택한 간선이 사이클을 형성하지 않는지 판단하는 로직입니다. 이번 문제는 간선이 양뱡항으로 연결을 가지는 무방향 그래프이므로 '유니온 파인드(union-find)' 알고리즘으로 쉽게 해결할 수 있습니다. 간단히 설명하면 두 노드가 다른 집합에 있을 때 사이클을 형성하지 않고, 같은 집합에 속해 있을 때 사이클을 형성한다는 원리를 사용한 것입니다. 더 궁금한 점이 있으신 분들은 한 번 찾아보는게 좋을 듯 합니다.

 하지만, 이 문제는 추가 요구사항이 하나 더 있습니다. 바로, 한 마을을 두 개의 마을로 나누어야 합니다. 한 마을을 두 개의 마을로 분리하기 위해서는 최소 비용 신장 트리에서 아무 한 간선만 제거하면 됩니다. 즉, 마을을 최소 비용으로 유지하기 위해 최소 신장 비용 트리에서 가장 큰 가중치를 가지는 간선을 제거하면 문제를 해결할 수 있습니다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

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

typedef pair<int, pair<int, int>> piii;

int n, m, parent[100004], ret, last;
priority_queue<piii, vector<piii>, greater<piii>> pq;
//루트 노드 반환
int getRoot(int node){
    if(node == parent[node]) return node;
    return parent[node] = getRoot(parent[node]); //경로 압축
}

int main() {
    //입출력 성능 향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    for(int i = 0; i <= n; i++) parent[i] = i; //노드 초기화
    
    int from, to, weight;
    for(int i = 0; i < m; i++){
        cin >> from >> to >> weight;
        pq.push({weight, {from, to}}); //{가중치, {시작, 도착}} 형태로 저장
    }

    while(!pq.empty()){
        weight = pq.top().first;
        tie(from, to) = pq.top().second;
        pq.pop();
        
        //사이클을 형성하는 경우
        if(getRoot(from) == getRoot(to)) continue;
        
        ret += weight;
        last = weight;
        //union
        parent[getRoot(to)] = getRoot(from);
    }
    cout << ret - last;
    return 0;
}

 그래프를 따로 구성하지는 않고 바로 간선을 우선순위 큐에 넣어 구현했습니다. 이때, 가중치 순으로 오름차순 정렬을 해야 하기 때문에 {가중치, {시작 노드, 도착 노드}} 형태로 저장했습니다.

 우선 순위 큐가 모두 빌 때까지 크루스칼 알고리즘을 실행합니다. 먼저 선택한 간선의 사이클 형성 여부를 판별하고 사이클을 형성하지 않았다면 ret에 가중치를 추가합니다. 이후 union 로직을 수행합니다. 이때, 반드시 각 노드의 루트 노드로 union 해야 합니다.

 크루스칼 알고리즘을 마치고 결과를 출력합니다. 이때, 최소 신장 트리에서 가장 큰 가중치를 가지는 간선은 제거해야 합니다. 간선 추가는 오름차순으로 진행되었기 때문에 가장 마지막에 추가된 간선을 제거하면 쉽게 구할 수 있습니다.

---