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

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
 
int N = 0;
int parent[100001] = {};
int ans = 0;
 
std::vector<std::pair<int, int>> X = {};
std::vector<std::pair<int, int>> Y = {};
std::vector<std::pair<int, int>> Z = {};
std::vector<std::tuple<int, int, int>> planet = {};
 
int FindParent(int x)
{
	if (parent[x] == x) 
		return x;
 
	else 
		return parent[x] = FindParent(parent[x]);
}
 
bool unionParent(int x, int y)
{
	x = FindParent(x);
	y = FindParent(y);
 
	if (x == y) 
		return false;
 
	else
	{
		parent[y] = parent[x];
		return true;
	}
}
 
int main()
{
	std::cin >> N;
 
	for (int i = 0; i < N; ++i)
	{
		parent[i] = i;
	}
 
	for (int i = 0; i < N; ++i)
	{
		int x = 0;
		int y = 0;
		int z = 0;
		std::cin >> x >> y >> z;
		X.push_back({ x,i });
		Y.push_back({ y,i });
		Z.push_back({ z,i });
	}
 
	sort(X.begin(), X.end());
	sort(Y.begin(), Y.end());
	sort(Z.begin(), Z.end());
 
	for (int i = 0; i < N - 1; ++i)
	{
		planet.push_back({ X[i + 1].first - X[i].first, X[i].second, X[i + 1].second });
		planet.push_back({ Y[i + 1].first - Y[i].first, Y[i].second, Y[i + 1].second });
		planet.push_back({ Z[i + 1].first - Z[i].first, Z[i].second, Z[i + 1].second });
	}
 
	sort(planet.begin(), planet.end());
 
	for (int i = 0; i < planet.size(); ++i)
	{
		int dist = std::get<0>(planet[i]);
		int x = std::get<1>(planet[i]);
		int y = std::get<2>(planet[i]);
 
		if (unionParent(x, y))
		{
			ans += dist;
		}
	}
 
	std::cout << ans;
 
	return 0;
}

이전에 풀어본 문제와 비슷합니다.

문제를 조금 어렵게 풀어만 놓은 거입니다.

X, Y, Z 중 가장 짧은 것만 확인하면 되기 때문에 짧은 순서대로 체크만 하면 됩니다.

짧은 순서대로 연결하면 최소 거리가 나오기 때문에 생각보다 쉽게 풀 수 있습니다.