문제
풀이
모든 정점을 잇는 최소 간선 가중치 합을 구하는 문제이다. 크루스칼 알고리즘을 사용한다. 이를 위해 모든 좌표간의 거리들을 구하여 넣은 Edge 벡터를 오름차순으로 sort한다. 제일 거리가 가까운 첫번째 간선부터 차례대로 집합 형성을 시도한다. 이 때, 사이클이 형성되는 집합은 형성하지 않으며 모든 간선에 대해 시도한다. 이를 통해 얻은 cost가 최종 답이 된다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
vector<pair<double, double>> map;
vector<pair<double, pair<int, int>>> edge;
int parent[101];
double dist(double x, double y, double xx, double yy){
double dist_x = (x-xx)*(x-xx);
double dist_y = (y-yy)*(y-yy);
double final_dist = sqrt(dist_x + dist_y);
return final_dist;
}
int find(int x){
if(parent[x] < 0) return x;
return parent[x] = find(parent[x]);
}
bool merge(int x, int y){
x = find(x);
y = find(y);
if(x == y) return false;
parent[x] = y;
return true;
}
int main(){
int n;
scanf("%d", &n);
for(int i = 0; i<=n; i++){
parent[i] = -1;
}
for(int i = 0; i<n; i++){
double a, b;
scanf("%lf %lf", &a, &b);
map.push_back(make_pair(a, b));
}
for(int i = 0; i<n; i++){
for(int j = i+1; j<n; j++){
int x = map[i].first;
int y = map[i].second;
int xx = map[j].first;
int yy = map[j].second;
double edge_dist = dist(x, y, xx, yy);
edge.push_back(make_pair(edge_dist, make_pair(i, j))); // i번째 좌표와 j번째 좌표의 거리
}
}
sort(edge.begin(), edge.end());
double cost = 0;
for(int i = 0; i<edge.size(); i++){
int x = edge[i].second.first;
int y = edge[i].second.second;
if(merge(x, y)){
cost += edge[i].first;
}
}
printf("%.2lf\n", cost);
}
