백준 2887번 : 행성 터널 - 크루스칼

https://www.acmicpc.net/problem/2887

2887번: 행성 터널

1.문제설명

두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.

INPUT

5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

OUTPUT

4

 

INPUT으로 N개의 행성의 x,y,z 좌표가 주어진다.

 

좌표를 바탕으로 최소 스패닝 트리를 만들어야한다.

 

단 간선의 길이가  min(|xA-xB|, |yA-yB|, |zA-zB|)이다.

 

 

 

 

---

 

 

 

2. 접근방법[알고리즘]

처음에 간선의 길이가 두 행성간 유클리드 거리인줄 알고 한참 고민했다.

 

이 문제에서 간선의 길이는 x좌표의 차이, y좌표의 차이, z 좌표의 차이 중 최솟값이다.

 

x,y,z 좌표를 각각 입력받고 sort하면 n이 10만이므로 nlogn으로 해결 할 수 있다.

 

그리고 각각 x좌표의 차이 y좌표의 차이 z좌표의 차이를

 

우선순위 큐에 넣고 Union & Find 해주면서

 

크루스칼 알고리즘의 방법으로 최소스패닝트리를 구할 수 있다.

 

 

 

 

---

 

 

3.문제풀이코드 C++

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

int unf[100001];

int Find(int x) {
	if (x == unf[x]) {
		return x;
	}
	else return unf[x] = Find(unf[x]);
}

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);
	if (a != b) {
		unf[a] = b;
	}
}

struct Edge {
	int x, y, val;
	bool operator<(const Edge& b)const {
		return val > b.val;
	}
};

vector<pair<int, int> > x, y, z;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 100001; i++) {
		unf[i] = i;
	}

	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		x.push_back({ a,i });
		y.push_back({ b,i });
		z.push_back({ c,i });
	}

	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	sort(z.begin(), z.end());

	priority_queue<Edge> Q;

	for (int i = 0; i < n - 1; i++) {
		int dif_x = x[i + 1].first - x[i].first;
		int dif_y = y[i + 1].first - y[i].first;
		int dif_z = z[i + 1].first - z[i].first;
		Q.push({ x[i + 1].second, x[i].second, dif_x });
		Q.push({ y[i + 1].second, y[i].second, dif_y });
		Q.push({ z[i + 1].second, z[i].second, dif_z });
	}

	int ans = 0;
	while (!Q.empty()) {
		int x = Q.top().x;
		int y = Q.top().y;
		int val = Q.top().val;
		Q.pop();

		if (Find(x) != Find(y)) {
			Union(x, y);
			ans += val;
		}
	}

	cout << ans << '\n';

	return 0;
}

 

백준 2887번