[C++] 백준 4386번: 별자리 만들기 (최소 신장 트리)

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

---

문제 이해하기

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

모든 별을 잇는 최소 비용을 구하여라.

---

시간복잡도 어림하기

최소 신장 트리(Minimum Spanning Tree)

 모든 노드(별)을 연결하는 최소 비용을 구하는 문제이므로 최소 비용으로 신장 트리를 구성하는 것과 같습니다. 최소 신장 트리를 구하는 알고리즘으로 Kruskal 알고리즘과 Prim 알고리즘 두 종류가 있습니다.

 Kruskal 알고리즘의 시간 복잡도는 O(eloge)이고, Prim 알고리즘의 시간 복잡도는 O(n^2) 입니다. 이번 문제에서 n의 최댓값은 100이고, e의 최댓값은 100 x 100 = 10000 이므로 둘 중 어느 알고리즘을 사용해도 해결할 수 있는 문제입니다. 이번에는 Kruskal 알고리즘을 사용하여 문제를 해결해 보겠습니다.

---

알고리즘 설계하기

 Kruskal 알고리즘은 다음 과정으로 진행합니다.

1. 그래프에 존재하는 모든 간선을 오름차순으로 정렬한다.
2. 가장 비용이 작은 간선을 선택한다.
2-1. 해당 간선이 사이클을 형성하는지 확인하고 사이클을 형성하지 않는 경우, 신장 트리에 추가한다.

 그래프의 모든 간선을 정렬할 때는 배열이나 vector를 사용해도 되지만, 우선순위 큐를 사용하는 것이 간편하여 우선순위 큐를 사용해봅시다.

 우선순위 큐에 저장할 데이터는 간선의 비용과, 간선을 양 끝 노드 정보가 필요합니다. 따라서 {cost, {left node, right node}} 와 같은 방식으로 pair를 두 개 중첩하여 사용합니다.

 여기서 cost는 어떻게 구하면 될까요?

 일반적인 문제라면 각 간선의 cost를 알려주는 경우가 많지만, 이번 문제는 각 점의 좌표만 알려줍니다. 따라서 이를 기반으로 간선의 비용을 구해야합니다. 

 문제에서 간선의 비용은 2차원 평면에서 두 점이 떨어진 거리와 같다고 했으므로 피타고라스 정리를 응용하여 다음과 같이 구할 수 있습니다.

두 점 a(x1, y1) b(x1, y2)에 대해
a와 b가 떨어진 거리 = sqrt((x1 - x2)^2 + (y1 - y2)^2) 
*sqrt : 2의 제곱근

이때, 결과는 double 자료형으로 구해지는데, 컴퓨터 연산 특성상 소수 계산은 반드시 오차가 발생합니다. 하지만, 문제에서 오차는 10^-2까지 허용한다고 했으므로 오차를 신경쓰지 않아도 됩니다.

 다음으로는 선택한 간선이 사이클을 형성하는지를 판단해야합니다. 무방향 그래프에서 사이클 여부 판단은 유니온 파인드(Union Find) 를 사용하여 쉽게 구할 수 있습니다.

 유니온 파인드는 이름 그대로 union 부분과 find 부분으로 나누는데 union은 두 노드를 하나의 트리로 합치는 과정을 말하고 find는 해당 노드의 루트 노드를 찾는 과정을 말합니다. 유니온 파인드에 대한 자세한 내용은 구글에 검색해보시면 좋을 것 같습니다. 

---

알고리즘 구현하기

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

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

int n, parent[104];
double ret;
pair<double, double> a[104];
priority_queue<pair<double, pair<int, int>>, vector<pair<double, pair<int, int>>>, greater<pair<double, pair<int, int>>>> pq;

/*node의 루트 값을 구하는 함수*/
int getRoot(int node){
    if(parent[node] == 0) return node;
    return parent[node] = getRoot(parent[node]); //경로 압축
}
int main(){
    scanf("%d", &n);
    double y, x;
    for(int i = 1; i <= n; i++){
        scanf("%lf %lf", &y, &x);
        a[i] = {y, x};
        /*현재 노드와 지금까지의 모든 노드 사이의 거리계산*/
        for(int j = i - 1; j >= 1; j--){
            double ty = a[j].first, tx = a[j].second;
            /*거리 계산*/
            pq.push({sqrt(pow(y - ty, 2) + pow(x - tx, 2)), {j, i}});
        }
    }

    /*Kruskal 알고리즘*/
    int from, to;
    double cost;
    while(!pq.empty()){
        cost = pq.top().first;
        tie(from, to) = pq.top().second;
        pq.pop();
        int r1 = getRoot(from);
        int r2 = getRoot(to);
        /*두 노드의 루트가 같음 -> 사이클 형성*/
        if(r1 == r2) continue;
        parent[r2] = r1; //트리 병합
        ret += cost;
    }
    printf("%.2lf", ret); //소수점 둘째자리까지 출력
    return 0;
}

 Kruskal 알고리즘 진행 중, 사이클 판단을 위해 반드시 각 노드의 루트 노드를 구해야합니다. 루트 노드를 사용하지 않고 부모 노드를 사용하게 되면 같은 트리임에도 불구하고 서로 다른 트리로 판단할 가능성이 있기 때문입니다.

---