[백준 2887] 행성 터널 (C++)

문제 링크: https://www.acmicpc.net/problem/2887

2887번: 행성 터널

1. 주의할 점

- MST 문제로, 프림 혹은 크루스칼 알고리즘에 대하여 알고 있어야 한다. 여기서는 크루스칼 사용

- X,Y,Z 정렬을 할 때마다 우선순위큐에 간선을 추가해야 한다(이 부분을 생각하지 못하여 다른 분들의 힌트를 통해 해결했다)

-> X,Y,Z로 정렬했을 때 인접한 간선과 가장 가까울 것이 자명하므로 인접한 간선과의 거리를 계산하여 우선순위큐에 추가한다

 

2. 구현

- Info의 형태를 지닌 배열에 입력값을 저장한다

- X,Y,Z의 순서대로 정렬을 하며 인접한 행성(Node)와의 X,Y,Z의 차이값 중에서 최소인 값, 시작 행성, 도착 행성을 저장하고 우선순위에 추가한다

- Par[] 배열을 전부 자기 자신이 부모가 되도록 초기화 한다

- Find_par(int X) 함수를 통해 X의 부모를 반환하도록 한다

- Make_union(int X, int Y) 함수를 통해 X,Y의 부모가 서로 다르다면, 부모의 숫자가 작은 값이 부모가 되도록 설정하여 서로 같은 부모를 두도록 한다

- 우선순위에 저장된 모든 간선의 정보를 빼면서 MST를 형성한다

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int cnt = 0;
struct info {
	long long x, y, z;
	int num;		//몇번 째 행성인지
};
bool cmp(info &a, info &b) {
	if (cnt == 0)	return a.x > b.x;
	else if (cnt == 1) return a.y > b.y;
	else if (cnt == 2) return a.z > b.z;
}
struct info2 {
	long long val;
	int from, to;
};
struct cmp2 {
	bool operator()(info2 &a, info2 &b) {
		return a.val > b.val;
	}
};
info tmp;
info2 tmp2;
info planet[100001];
int par[100001];

int find_parent(int x) {
	if (par[x] == x) return x;
	else
		return par[x] = find_parent(par[x]);
}

void make_union(int x, int y) {
	x = find_parent(x);
	y = find_parent(y);
	if (x < y) par[y] = x;
	else if (x > y) par[x] = y;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int node;
	long long result = 0;
	cin >> node;
	for (int i = 0; i < node; i++) {
		cin >> planet[i].x >> planet[i].y >> planet[i].z;
		planet[i].num = i;
	}
	priority_queue<info2, vector<info2>, cmp2> pq;
	for (int i = 0; i < 3; i++) {
		sort(planet, planet + node, cmp);
		cnt++;
		for (int j = 0; j < node - 1; j++) {
			long long val = min(abs(planet[j].x - planet[j + 1].x),
				min(abs(planet[j].y - planet[j + 1].y), abs(planet[j].z - planet[j + 1].z)));
			tmp2.val = val;
			tmp2.from = planet[j].num;
			tmp2.to = planet[j + 1].num;
			pq.push(tmp2);
		}
	}
	for (int i = 0; i < node; i++) 
		par[i] = i;
	
	while (!pq.empty()) {
		int from = pq.top().from;
		int to = pq.top().to;
		long long val = pq.top().val;
		pq.pop();
		int p1 = find_parent(from);
		int p2 = find_parent(to);
		if (p1 == p2) continue;
		make_union(from, to);
		result += val;
	}
	cout << result;
	return 0;
}