백준2887 행성 터널

작성일 | In

문제 링크

  • http://icpc.me/2887

문제 출처

  • 2009/2010 COCI Contest #7 4번

사용 알고리즘

  • MST

풀이

모든 행성 사이에 간선을 만들어주면 O(N2)으로 시간 초과가 나게 됩니다.
결론부터 말하자면, 3*(N-1)개의 간선만 봐도 MST를 항상 만들 수 있습니다.

x축만 있다고 봅시다.
좌표를 기준으로 정렬을 한 뒤, i번째 행성과 i+1번째 행성을 이어주면 N-1개의 간선으로 MST를 만들 수 있습니다.
이 방법 외에는 MST를 만드는 방법이 없습니다.

3차원으로 올려봅시다.
각 축에 대해 위에서 언급한 작업을 수행해주면 3*(N-1)개의 간선만 보게 됩니다.
x축만 있을 때와 동일한 이유로 MST를 항상 찾을 수 있습니다.

전체 코드

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
82
83
84
85
86
87
88
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;

typedef long long ll;

struct Edge{
	ll s, e, x;
	Edge(){}
	Edge(ll s, ll e, ll x) : s(s), e(e), x(x) {}
	bool operator < (Edge &rhs){
		return x < rhs.x;
	}
};

struct Planet{
	ll x, y, z, idx;
	Planet(){}
	Planet(ll x, ll y, ll z) : x(x), y(y), z(z) {}
};

bool cmpX(Planet &a, Planet &b){
	return a.x < b.x;
}

bool cmpY(Planet &a, Planet &b){
	return a.y < b.y;
}

bool cmpZ(Planet &a, Planet &b){
	return a.z < b.z;
}

int par[101010];
int rnk[101010];

void init(){
	for(int i=0; i<101010; i++) par[i] = i, rnk[i] = 1;
}

int find(int v){
	if(v == par[v]) return v;
	return par[v] = find(par[v]);
}

bool merge(int u, int v){
	u = find(u), v = find(v);
	if(u == v) return 0;
	if(rnk[u] > rnk[v]) swap(u, v);
	par[u] = v;
	if(rnk[u] == rnk[v]) rnk[v]++;
	return 1;
}

vector<Planet> arr;
vector<Edge> v;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	init();
	int n; cin >> n; arr.resize(n);
	for(int i=0; i<n; i++) arr[i].idx = i, cin >> arr[i].x >> arr[i].y >> arr[i].z;

	sort(all(arr), cmpX);
	for(int i=1; i<n; i++){
		v.push_back({arr[i-1].idx, arr[i].idx, arr[i].x - arr[i-1].x});
	}

	sort(all(arr), cmpY);
	for(int i=1; i<n; i++){
		v.push_back({arr[i-1].idx, arr[i].idx, arr[i].y - arr[i-1].y});
	}

	sort(all(arr), cmpZ);
	for(int i=1; i<n; i++){
		v.push_back({arr[i-1].idx, arr[i].idx, arr[i].z - arr[i-1].z});
	}

	sort(v.begin(), v.end());

	ll ans = 0;
	for(auto i : v){
		if(merge(i.s, i.e)){
			ans += i.x;
		}
	}
	cout << ans;
}