문제
풀이
MST를 구하는 문제이다. N^2으로 각각의 dist를 모두 구해서 sort한 다음 크루스칼 알고리즘을 적용하면 메모리 초과로 인해 실패하게 된다. 이 문제에서는 단순히 x, y, z좌표 각각의 차이의 min값을 distance로 정의하고 있기에, x, y, z값들을 sort하여 각각 인접한 사이의 거리들을 edge 벡터에 넣는다. 그 이후에 sort를 하고 난 뒤, edge.size()까지 크루스칼을 진행한다. 최소 신장 트리를 구하는 문제이기 때문에 x, y, z 좌표 각각을 오름차순으로 정렬한 뒤 이웃간의 거리를 구해서 작은 순서대로 이어 붙이는 식이 최소 신장 트리를 만족하게 된다.
소스 코드
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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<tuple<int, int, int>> testcase;
vector<tuple<int, int, int>> edge;
vector<pair<int, int>> X;
vector<pair<int, int>> Y;
vector<pair<int, int>> Z;
int parent[100001];
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++){
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
X.push_back(make_pair(x, i));
Y.push_back(make_pair(y, i));
Z.push_back(make_pair(z, i));
}
sort(X.begin(), X.end());
sort(Y.begin(), Y.end());
sort(Z.begin(), Z.end());
for(int i = 0; i<N-1; i++){
edge.push_back({X[i+1].first - X[i].first, X[i+1].second, X[i].second});
edge.push_back({Y[i+1].first - Y[i].first, Y[i+1].second, Y[i].second});
edge.push_back({Z[i+1].first - Z[i].first, Z[i+1].second, Z[i].second});
}
sort(edge.begin(), edge.end());
int cost = 0;
for(int i = 0; i<edge.size(); i++){
if(merge(get<1>(edge[i]), get<2>(edge[i]))) cost += get<0>(edge[i]);
}
printf("%d\n", cost);
}
