[백준 2887] 행성터널

문제

www.acmicpc.net/problem/2887

2887번: 행성 터널

 

문제 풀이

1. 두 점을 연결하는 비용은 각 x, y, z좌표끼리 차의 최소 값이므로 N개의 행성을 연결하려면 좌표끼리의 차를 값으로 가지는 N - 1개의 간선을 찾아야 합니다.

 

2. 이는 아래의 관찰을 통해 각 축에 대해서 좌표를 정렬했을 때 인접한 점들의 차만 간선에 추가하는 방법을 통해 해결했습니다.

• 서로 인접한 세 점 A, B, C에 대해 모든 점을 연결할 때, ①은 A, C, B 순으로 ②은 A, B, C순으로 연결할 때의 총길이라고 한다. (① |AC| + |BC|, ② |AB| + |BC|)

• 간선에 추가하는 좌표끼리의 차는 최소 값을 가져야 하고, |AC| > |AB|이므로 서로 인접한 점들의 좌표 차를 간선에 추가한다.

3. 이렇게 구한 간선들 중 혹시나 임의의 점 A, B에 대해서 x좌표의 차, y좌표의 차, z좌표의 차 중에서 같은 값이 존재해 두 점을 잇는 간선이 중복해서 추가되지 않을까 생각할 수 있으나 이는 merge할 때 다른 점들에 대해서만 연결하게 하므로 일어나지 않습니다.

 

코드

#include <bits/stdc++.h>
using namespace std;

struct P {
	int x, y, z, idx;
	P(int x1, int y1, int z1, int i1) : x(x1), y(y1), z(z1), idx(i1) {}
};

struct edge {
	int u, v, w;
	edge(int u1, int v1, int w1) : u(u1), v(v1), w(w1) {}
	bool operator <(edge& o) {
		return w < o.w;
	}
};
int n, a, b, c, ans, cnt;
vector<P> v;
vector<int> p;
vector<edge> e;
int find(int x) {
	if (p[x] < 0) return x;
	return p[x] = find(p[x]);
}

bool merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return 0;
	p[v] = u;
	return 1;
}

bool cmp1(P i, P j) { return i.x < j.x; }
bool cmp2(P i, P j) { return i.y < j.y; }
bool cmp3(P i, P j) { return i.z < j.z; }

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;
	p.resize(n, -1);
	for (int i = 0; i < n; i++) {
		cin >> a >> b >> c;
		v.push_back({ a,b,c,i });
	}
	sort(v.begin(), v.end(), cmp1);
	for (int i = 1; i < n; i++) e.push_back(edge(v[i].idx, v[i - 1].idx, abs(v[i].x - v[i - 1].x)));
	sort(v.begin(), v.end(), cmp2);
	for (int i = 1; i < n; i++) e.push_back(edge(v[i].idx, v[i - 1].idx, abs(v[i].y - v[i - 1].y)));
	sort(v.begin(), v.end(), cmp3);
	for (int i = 1; i < n; i++) e.push_back(edge(v[i].idx, v[i - 1].idx, abs(v[i].z - v[i - 1].z)));

	sort(e.begin(), e.end());
	for (int i = 0;; i++) {
		if (merge(e[i].u, e[i].v)) {
			ans += e[i].w;
			cnt++;
			if (cnt == n - 1) break;
		}
	}
	cout << ans;
}