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

링크

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

2887번: 행성 터널

해설

최소 신장 트리 문제입니다.

그런데 다른 문제들과는 조금 다르게 모든 노드들이 다 연결되어있는 상태라

기존의 방법대로 kruskal 알고리즘을 적용시키면 약 N^2 개의 공간이 필요해서 메모리 초과가 됩니다.

 

이 문제의 특징은 x y z 축의 값중 가장 작은 값이 최소 비용이 된다는 것입니다.

즉 kruskal 알고리즘을 적용할 때 모든 노드를 볼 필요가 없고 근처에 있는 후보가 될만한 것들 만 골라서

적용시켜야 합니다.

 

이 근처에 있는 후보들을 뽑는 방법이 각 축에 대해 정렬하게되면 바로 옆에 있는 노드들이 후보가 되게 됩니다.

 

각 축에 대해 후보들을 모두 뽑아서 kruskal 알고리즘을 적용하면 됩니다.

 

아래 코드에 모두 구현되어있습니다.

 

코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

struct edge {
	int len, a, b;
};

bool operator < (edge& _a, edge& _b) {
	return _a.len < _b.len;
}

struct xyz {
	int x, y, z, idx;
};

bool comp_x(xyz _a, xyz _b) {
	return _a.x < _b.x;
}

bool comp_y(xyz _a, xyz _b) {
	return _a.y < _b.y;
}

bool comp_z(xyz _a, xyz _b) {
	return _a.z < _b.z;
}

int N, DIST = 0, parent[100000], set_size[100000];
xyz TABLE[100000];

int abs(int _a) {
	if (_a < 0)
		return -_a;
	return _a;
}


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

	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> TABLE[i].x >> TABLE[i].y >> TABLE[i].z;
		TABLE[i].idx = i;
		parent[i] = i;
		set_size[i] = 1;
	}

	vector<edge> list;
	list.reserve(N * 3);

	sort(TABLE, TABLE + N, comp_x);
	for (int i = 1; i < N; ++i)
		list.push_back({ abs(TABLE[i].x - TABLE[i-1].x), TABLE[i].idx, TABLE[i - 1].idx });
	
	sort(TABLE, TABLE + N, comp_y);
	for (int i = 1; i < N; ++i)
		list.push_back({ abs(TABLE[i].y - TABLE[i - 1].y), TABLE[i].idx, TABLE[i - 1].idx });

	sort(TABLE, TABLE + N, comp_z);
	for (int i = 1; i < N; ++i)
		list.push_back({ abs(TABLE[i].z - TABLE[i - 1].z), TABLE[i].idx, TABLE[i - 1].idx });
	
	sort(list.begin(), list.end());

	for (int i = 0; i < list.size(); ++i) {
		int left_p = list[i].a, right_p = list[i].b;

		while (left_p != parent[left_p])
			left_p = parent[left_p];

		while (right_p != parent[right_p])
			right_p = parent[right_p];

		if (left_p == right_p)
			continue;

		if (set_size[left_p] > set_size[right_p])
			swap(left_p, right_p);
		parent[left_p] = right_p;
		DIST += list[i].len;
		set_size[right_p] += set_size[left_p];
		if (set_size[right_p] == N)
			break;
	}

	cout << DIST;

	return 0;
}