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

문제

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.
별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

예제 입출력

• 예제 입력 1

3
1.0 1.0
2.0 2.0
2.0 4.0

• 예제 출력 1

3.41

Solution

두 가지 방법을 사용할 수 있다.

1. Kruskal Algorithm

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define MAX 101
using namespace std;

vector<pair<double, double>> pointData;
vector<pair<double, pair<double, double>>> edge;
int Parent[MAX];

int getParent(int num){
    if(num == Parent[num]) return num;
    return Parent[num] = getParent(Parent[num]);
}

void unionParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a != b) Parent[a] = b;
}

bool findParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a == b) return true;
    else return false;
}

double kruskal(){
    double result = 0;
    sort(edge.begin(), edge.end());
    for(int i = 0; i < edge.size(); i++){
        double cost = edge[i].first;
        int a = edge[i].second.first;
        int b = edge[i].second.second;
        if(!findParent(a, b)){
            unionParent(a, b);
            result += cost;
        }
    }
    return result;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    for(int i = 0; i < MAX; i++) Parent[i] = i;
    int N; cin >> N;
    for(int i = 1; i <= N; i++){
        double a, b;
        cin >> a >> b;
        pointData.push_back({a, b});
    }
    for(int i = 0; i < N; i++){
        double x = pointData[i].first;
        double y = pointData[i].second;
        for(int j = i + 1; j < N; j++){
            double xx = pointData[j].first;
            double yy = pointData[j].second;

            double dx = pow((x - xx),2);
            double dy = pow((y - yy), 2);
            double dist = sqrt(dx + dy);
            edge.push_back({dist, {i, j}});
        }
    }

    double answer = kruskal();
    cout << answer << '\n';
}

코드가 겁나 길다. 크루스칼 알고리즘을 쓸 수 있도록 데이터들을 처리해주는 데 시간이 필요하다.
이 문제를 건드릴 정도면 크루스칼 알고리즘 정도는 이해하고 있을 가능성이 높다. 그래도 혹시 모르니 간략하게 설명하면 다음과 같다.

가능한 모든 경로들을 비용 순으로 오름차순 정렬한 후 Union Find 알고리즘을 통해 MST(Minimum Spanning Tree) 를 만들어 준다.

좌표들은 모두 입력받았다. 중요한 건, 이 좌표들을 경로들로 만들어야 한다는 것.

우선 입력받은 데이터들에 대해 모든 경로를 구해야 한다.

어차피 데이터가 많아봐야 100개다. $O(N^2)$라고 한들 뭐 어쩌겠는가?

vector<pair<double, double>> pointData;
vector<pair<double, pair<double, double>>> edge;
int Parent[MAX];

int getParent(int num){
    if(num == Parent[num]) return num;
    return Parent[num] = getParent(Parent[num]);
}

void unionParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a != b) Parent[a] = b;
}

bool findParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a == b) return true;
    else return false;
}

pointData는 좌표들의 데이터, edge는 경로들의 데이터다. 크루스칼 알고리즘이니까 Union Find에 필요한 함수들과 각 노드들 Parent 배열이 필요하겠지.

for(int i = 0; i < MAX; i++) Parent[i] = i;
int N; cin >> N;
for(int i = 1; i <= N; i++){
    double a, b;
    cin >> a >> b;
    pointData.push_back({a, b});
}

사전 작업을 해 준다. 모든 노드들(좌표들)의 Parent값을 본인으로 셋업해주고 모든 좌표값을 입력받는다.

 for(int i = 0; i < N; i++){
    double x = pointData[i].first;
    double y = pointData[i].second;
    for(int j = i + 1; j < N; j++){
        double xx = pointData[j].first;
        double yy = pointData[j].second;

        double dx = pow((x - xx),2);
        double dy = pow((y - yy), 2);
        double dist = sqrt(dx + dy);
        edge.push_back({dist, {i, j}});
    }
}

double answer = kruskal();
cout << answer << '\n';

그 후 모든 좌표 데이터에 대해 경로를 구해준다. 두 점간의 거리 구하는 공식에 대해 설명 하지는 않겠다.
edge 데이터는 총 두개의 pair로 이루어진 가변배열(vector)이다. 비용, 노드 번호를 저장하기 위해서.

double kruskal(){
    double result = 0;
    sort(edge.begin(), edge.end());
    for(int i = 0; i < edge.size(); i++){
        double cost = edge[i].first;
        int a = edge[i].second.first;
        int b = edge[i].second.second;
        if(!findParent(a, b)){
            unionParent(a, b);
            result += cost;
        }
    }
    return result;
}

크루스칼 알고리즘은 뭐 크게 어렵지 않다. 우선 edge를 정렬한다. cost가 가변배열 노드에서 데이터 우선순위가 높기 때문에 cost 기준으로 정렬이 된다.
그 후 하나 하나 서치하면서 해당 경로, 시작 노드, 끝 노드를 가져와서 unionfind 알고리즘을 시행한다. unionParent 함수가 시행된다면 해당 cost를 사용했다는 의미이므로 result에 추가한다. 모든 탐색이 끝나면 return 한다.

2. Prim Algorithm

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#define MAX 101
using namespace std;

vector<pair<double, double>> pointData;
vector<pair<int, double>> edge[MAX];
bool visited[MAX];

double prim(){
    double result = 0;
    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> PQ;
    PQ.push({0, 0});
    while(!PQ.empty()){
    	int next = PQ.top().second;
        double minCost = PQ.top().first;
        PQ.pop();
    	if(!visited[next]){
        	visited[next] = true;
            result += minCost;
            for(auto X : edge[next]){
                if(!visited[X.first]) PQ.push({X.second, X.first});
            }
        }
    }
    return result;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N; cin >> N;
    for(int i = 0; i < N; i++){
        double a, b;
        cin >> a >> b;
        pointData.push_back({a, b});
    }
    for(int i = 0; i < N; i++){
        double x = pointData[i].first;
        double y = pointData[i].second;
        for(int j = i + 1; j < N; j++){
            double xx = pointData[j].first;
            double yy = pointData[j].second;
            
            double dx = pow((x - xx),2);
            double dy = pow((y - yy), 2);
            double dist = sqrt(dx + dy);
            edge[i].push_back({j, dist});
            edge[j].push_back({i, dist});
        }
    }
    double answer = prim();
    cout << answer << '\n';
}

데이터 입력받는 건 같다. 하지만 문제를 잘 보면 알겠지만 단방향 그래프가 아니다.
프림 알고리즘 또한 아마 다들 알고있기는 하겠지만 간단히 설명하면 다음과 같다.

우선순위 큐를 활용하여 기준점이 되는 노드부터 탐색을 시작한다. 우선 순위 큐 내에 방문 한 노드에 대한 데이터가 있다면 빼버리고 남아있는 데이터 중 TOP에 존재하는 노드에 대한 경로 정보를 통해 해당 노드를 통해 갈 수 있는 노드들에 대한 데이터를 우선순위 큐에 갱신하고 해당 노드는 방문 처리 한다.

for(int i = 0; i < N; i++){
    double x = pointData[i].first;
    double y = pointData[i].second;
    for(int j = i + 1; j < N; j++){
        double xx = pointData[j].first;
        double yy = pointData[j].second;
            
        double dx = pow((x - xx),2);
        double dy = pow((y - yy), 2);
        double dist = sqrt(dx + dy);
        edge[i].push_back({j, dist});
        edge[j].push_back({i, dist});
    }
}

단방향 그래프가 아니기때문에 입력받는 과정에서 약간의 차이가 있다. i와 j 두 가지 노드에 대해 경로 데이터를 갱신해준다. i에서j로 가는, 그리고 j에서 i로 가는.

vector<pair<double, double>> pointData;
vector<pair<int, double>> edge[MAX];
bool visited[MAX];

그래서 edge 데이터도 다르다. Kruskal Algorithm을 사용할 때는 해당 경로 자체를 가변행렬에 집어넣었다면, Prim Algorithm은 마치 Adjacency Matrix처럼 특정 노드와 연결 된 경로들의 데이터가 저장 된다. 각 노드별 방문을 확인하는 visited boolean 배열 또한 필요하다.

double prim(){
    double result = 0;
    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> PQ;
    PQ.push({0, 0});
    while(!PQ.empty()){
    	int next = PQ.top().second;
        double minCost = PQ.top().first;
        PQ.pop();
    	if(!visited[next]){
        	visited[next] = true;
            result += minCost;
            for(auto X : edge[next]){
                if(!visited[X.first]) PQ.push({X.second, X.first});
            }
        }
    }
    return result;
}

본격적으로 Prim Algorithm 코드를 살펴보자. 제일 처음에는 0번 노드, 비용은 없음부터 시작한다.
while 문을 통해 구현한다. TOP에 있는 데이터를 기반으로 다음에 탐색 할 데이터를 갱신하고 해당 경로를 방문한 후, 해당 노드 기준으로 탐색 가능한 모든 경로를 PQ에 갱신한다.

마치 BFS와 흡사하다. Prim Algorithm은 이런 양방향 그래프인 상황에서 사용 할 수 있다. Kruskal Algorithm은 전체 경로를 크게 위에서 보면서 맞추는 느낌이라면 Prim Algorithm은 실제로 탐색을 시켜보는 방식이다.

Outro

두 알고리즘은 각자 특징에 맞게 써야한다.

Kruskal Algorithm

1. 간선 위주의 알고리즘
2. 정렬하는 데 시간이 걸릴 수 있다.
3. 간선의 갯수가 작을 때 유리하다.

Prim Algorithm

1. 정점 위주의 알고리즘
2. 최소 거리의 정점을 찾는 데 우선순위 큐에 의존한다.
3. 간선의 갯수가 많을 때 유리하다.