[백준/BOJ] 백준 2887번 : 행성 터널

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

2887번: 행성 터널

크루스칼 알고리즘을 이용하여 문제를 해결했다. x, y, z 좌표를 각각 정렬 후 x, y, z 좌표가 인접한 것(가까운 것)끼리 edge를 만든 뒤 크루스칼 알고리즘을 이용하였다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <stdlib.h>
using namespace std;

int n;
vector<pair<int, pair<int, int>>> edge;
vector<pair<int, int>> x;
vector<pair<int, int>> y;
vector<pair<int, int>> z;
int parent[100001];
int height[100001];

void Pre()
{
	for (int i = 1; i <= n; i++)
	{
		parent[i] = i;
		height[i] = 0;
	}
}

//유니온 파인드의 find
int Find(int node)
{
	if (parent[node] == node)
		return node;

	return parent[node] = Find(parent[node]);
}

//유니온 파인드의 유니온
void Merge(int node1, int node2)
{
	node1 = Find(node1);
	node2 = Find(node2);

	if (node1 == node2)
		return;

	//높이가 큰 것으로 합쳐진다
	if (height[node1] < height[node2])
		parent[node1] = node2;

	else
	{
		parent[node2] = node1;

		//높이가 같은것 끼리 합쳐지면 높이가 증가한다
		if (height[node1] == height[node2])
			height[node1]++;
	}
}


int Solve()
{
	Pre();

	int ret = 0;

	sort(edge.begin(), edge.end());

	for (int i = 0; i < edge.size(); i++)
	{
		int u = edge[i].second.first;
		int v = edge[i].second.second;
		int cost = edge[i].first;

		if (Find(u) != Find(v))
		{
			Merge(u, v);
			ret += cost;
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int input_x, input_y, input_z;

	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		//x,y,z 를 각각 저장한다
		cin >> input_x >> input_y >> input_z;
		x.push_back(make_pair(input_x, i));
		y.push_back(make_pair(input_y, i));
		z.push_back(make_pair(input_z, i));
	}

	//정렬한다
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	sort(z.begin(), z.end());

	int u, v, cost;
	for (int i = 1; i < n; i++)
	{
		//x,y,z 좌표가 인접한것 끼리 edge를 만든다
		u = x[i - 1].second;
		v = x[i].second;
		cost = abs(x[i - 1].first - x[i].first);
		edge.push_back(make_pair(cost, make_pair(u, v)));

		u = y[i - 1].second;
		v = y[i].second;
		cost = abs(y[i - 1].first - y[i].first);
		edge.push_back(make_pair(cost, make_pair(u, v)));

		u = z[i - 1].second;
		v = z[i].second;
		cost = abs(z[i - 1].first - z[i].first);
		edge.push_back(make_pair(cost, make_pair(u, v)));
	}

	cout << Solve();

	return 0;
}