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

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

2887번: 행성 터널

거리상 가장 가까운 것만 따지면 된다고 생각해서 x,y,z 따로따로 배열을 구한 후 정렬한 다음 각 값끼리 비교 연산해주면 된다고 생각했는데 그저 정렬이니까 값이 차이가 큰 것끼리 인접할 수 있다는 것을 알아차렸다. 마땅한 풀이가 생각이 안 나서 다른 분의 풀이를 보다가 정렬 후 인접한 두 점의 차를 저장하는 배열을 만드는 것을 보고 바로 풀이법을 떠올렸다. x,y,z 각각 인접한 점끼리의 차(가중치)를 배열에 저장하고 이 배열을 정렬 후 union-find로 싸이클이 만들어지는지만 따지면 된다.

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <memory.h>
#include <vector>

#define endl '\n'
#define ll long long
#define pii pair<int, int>
#define cout std::cout
#define maxNum 2100000000

using namespace std;

int N;
vector<pii> planet[3];
int parent[100000];
vector<pair<int, pii>> dist;

int findParent(int node) {
	if (parent[node] == node)
		return node;
	return parent[node] = findParent(parent[node]);
}

void unionParent(int node1, int node2) {
	node1 = findParent(node1);
	node2 = findParent(node2);
	if (node1 > node2) {
		parent[node2] = node1;
	}
	else {
		parent[node1] = node2;
	}
}

bool compare(pii a, pii b) {
	return a.second < b.second;
}

bool compare2(pair<int,pii> a, pair<int,pii> b) {
	return a.first < b.first;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N;
	int tmp1, tmp2, tmp3;
	for (int i = 0; i < N; i++) {
		cin >> tmp1 >> tmp2 >> tmp3;
		parent[i] = i;
		planet[0].emplace_back(i, tmp1);
		planet[1].emplace_back(i, tmp2);
		planet[2].emplace_back(i, tmp3);
	}
	sort(planet[0].begin(), planet[0].end(), compare);
	sort(planet[1].begin(), planet[1].end(), compare);
	sort(planet[2].begin(), planet[2].end(), compare);
	int i = 0;
	while (i != N-1) {
		int num1 = maxNum, num2 = maxNum, num3 = maxNum;
		num1 = abs(planet[0][i].second - planet[0][i + 1].second);
		dist.push_back({ num1,{planet[0][i].first,planet[0][i + 1].first} });
		num2 = abs(planet[1][i].second - planet[1][i + 1].second);
		dist.push_back({ num2,{planet[1][i].first,planet[1][i + 1].first} });
		num3 = abs(planet[2][i].second - planet[2][i + 1].second);
		dist.push_back({ num3,{planet[2][i].first,planet[2][i + 1].first} });
		i++;
	}
	sort(dist.begin(), dist.end(), compare2);
	i = 0;
	int ans = 0;
	int n = 0;
	while (n != N - 1) {
		if (findParent(dist[i].second.first) != findParent(dist[i].second.second)) {
			unionParent(dist[i].second.first, dist[i].second.second);
			ans += dist[i].first;
			n++;
		}
		i++;	
	}
	cout << ans << endl;
	return 0;
}