BOJ 2887. 행성 터널

🙇‍♀️[Platinum V] 행성 터널 - 2887

문제 링크

성능 요약

메모리: 15660 KB, 시간: 96 ms

분류

그래프 이론, 최소 스패닝 트리, 정렬

제출 일자

2024년 3월 6일 13:42:12

문제 설명

때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.

행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(x_A, y_A, z_A)와 B(x_B, y_B, z_B)를 터널로 연결할 때 드는 비용은 min(|x_A-x_B|, |y_A-y_B|, |z_A-z_B|)이다.

민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -10⁹보다 크거나 같고, 10⁹보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.

출력

첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.

🚀풀이

kruskal알고리즘을 이용해서 문제를 풀려고했다.

각 정점의 비용들을 비교하면서 풀려고 했는데 최대 정점이 10만개여서 모든 정점을 이을시에 메모리 초과가 났다.

문제의 핵심은 모든 정점의 거리를 비교하지 말고 근처에 있는 정점들만 비교를 해서 연결 정보를 넣어줘야했다.

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

// 행성 터널
// kruskal 문제

struct Edge
{
	int cost;
	int u, v;
	bool operator<(Edge& other)
	{
		return cost < other.cost;
	}
};

const int MAX = 111111;
int unf[MAX];
int n;
vector<pair<int, int>> v[3];
vector<Edge> planet;

int Find(int u)
{
	if (u == unf[u])
		return u;
	return unf[u] = Find(unf[u]);
}

void Merge(int u, int v)
{
	u = Find(u);
	v = Find(v);

	if (u == v)
		return;

	unf[u] = v;
}

void solve()
{
	cin >> n;
	int x, y, z;

	for (int i = 0; i < n; ++i)
	{
		cin >> x >> y >> z;
		v[0].push_back({ x, i });
		v[1].push_back({ y, i });
		v[2].push_back({ z, i });
		unf[i] = i;
	}

	sort(v[0].begin(), v[0].end());
	sort(v[1].begin(), v[1].end());
	sort(v[2].begin(), v[2].end());

	for (int i = 0; i < n - 1; ++i)
	{
		planet.push_back({ abs(v[0][i].first - v[0][i + 1].first), v[0][i].second, v[0][i + 1].second});
		planet.push_back({ abs(v[1][i].first - v[1][i + 1].first), v[1][i].second, v[1][i + 1].second});
		planet.push_back({ abs(v[2][i].first - v[2][i + 1].first), v[2][i].second, v[2][i + 1].second});
	}

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

	int ret = 0;
	for (int i = 0; i < planet.size(); ++i)
	{
		if (Find(planet[i].u) == Find(planet[i].v))
			continue;

		ret += planet[i].cost;
		Merge(planet[i].u, planet[i].v);
	}

	cout << ret;
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}