[C/C++] 백준 2887번 - 행성 터널 (MST, 크루스칼 알고리즘)

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
#include<tuple>
using namespace std;

int N, x, y, z;
int parent[100001];
int ans;
vector<pair<int, int>> X;
vector<pair<int, int>> Y;
vector<pair<int, int>> Z;
vector<tuple<int, int, int>> planet;

int find(int u)
{
	if (parent[u] == u) return u;
	else return parent[u] = find(parent[u]);
}

bool union_node(int u, int v)
{
	u = find(u);
	v = find(v);

	// 부모 노드가 같다면 싸이클이 생기므로 건너뜀
	if (u == v) return false;
	else
	{
		parent[u] = v; // 부모 노드 지정
		return true;
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	// 자기 자신을 부모로 지정
	for (int i = 0; i < N; i++)
		parent[i] = i;

	// 행성 좌표 입력받기
	for (int i = 0; i < N; i++)
	{
		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 d = get<0>(planet[i]);
		int u = get<1>(planet[i]);
		int v = get<2>(planet[i]);
		
		if (union_node(u, v)) ans += d;
	}

	cout << ans;
}

 

풀이 방법

planet<tuple<int, int, int>> : { 거리, 행성1, 행성2 } 저장하는 벡터

크루스칼 알고리즘은 모든 간선에 대해서 가중치가 작은 간선들부터 연결해주되 중간중간에 사이클이 생기게 된다면 건너뛰고 다음 간선을 연결하여 최소 스패닝 트리를 만들어가는 알고리즘입니다.

그러나 이 문제에서는 행성의 개수가 10만개 이므로 각각의 행성들의 거리를 벡터에 담으면 10만*10만으로 메모리 초과가 발생할 수 있습니다. 따라서 각각의 행성 X, Y, Z좌표의 차이들을 planet 벡터에 푸쉬하고 유니온 파인드를 하여 스패닝 트리를 찾을 수 있습니다.

 

 

www.acmicpc.net/problem/2887

2887번: 행성 터널