BOJ 2887 행성 터널

사용한 알고리즘

알고리즘 설명

행성간에 거리는 min(abs(X_i - X_j), abs(Y_i - Y_j), abs(Z_i - Z_j)) 임에 주목한다.
위에 행성 간에 거리를 이용하면 각각 X, Y, Z 축을 sorting 한 뒤에 좌표별 인접한 행성의 edge만 바라보면 된다.
모든 생성을 하기엔 edge가 O(N^2)으로 너무 많으며 위에 방법으로 O(3N)으로 줄일 수 있다.
위 edge들로 MST를 구성한다.

풀이

// baekjoon 2887 yechan
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

const int MAX_N=100001;

int N, x, y, z, root[MAX_N];
P posX[MAX_N], posY[MAX_N], posZ[MAX_N];
vector<pair<ll,P> > edge;

// Union-find for MST
int find(int x) {
	if (!root[x]) return x;
	return root[x] = find(root[x]);
}

bool merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return false;
	root[b] = a;
	return true;
}

int main() {
	scanf("%d", &N);
	for (int i=1; i<=N; i++) {
		scanf("%d%d%d", &x, &y, &z);
		posX[i] = P(x, i);
		posY[i] = P(y, i);
		posZ[i] = P(z, i);
	}

	sort(posX+1, posX+N+1);
	sort(posY+1, posY+N+1);
	sort(posZ+1, posZ+N+1);
	// 3N개의 Edge를 추가한다.
	for (int i=1; i<N; i++) {
		// edge의 data format: (ll, (int, int)) = (행성 A와 B 사이 거리, (행성 A, 행성 B))
		edge.push_back(make_pair(posX[i+1].first-posX[i].first, P(posX[i].second, posX[i+1].second)));
		edge.push_back(make_pair(posY[i+1].first-posY[i].first, P(posY[i].second, posY[i+1].second)));
		edge.push_back(make_pair(posZ[i+1].first-posZ[i].first, P(posZ[i].second, posZ[i+1].second)));
	}

	// MST 알고리즘
	sort(edge.begin(), edge.end());
	ll ret = 0;
	for (int i=0; i<edge.size(); i++) {
		if (merge(edge[i].second.first, edge[i].second.second)) {
			ret += edge[i].first;
		}
	}
	printf("%lld\n", ret);
	return 0;
}