백준/2887/MST/행성 터널

백준/2887/MST/행성 터널

문제 해석

모든 행성이 연결 될 수 있는 간선간의 최소 거리를 구하는 문제입니다.

문제 풀이

이 문제의 핵심은 메모리 초과를 피하는것입니다.
별자리 만들기
위에 문제를 푼것과 같이 모든 경우의 수를 담아 문제를 해결하려 하면 행성의 수가 최악의 수 100'000 일때 N*N 의 경우의 수가 나와 128MB을 아득히 넘어가는 숫자가 나옵니다.

이를 해결 하기 위해 3 * N의 경우의 수로만 문제를 해결하는 방법이 있습니다.
즉, X,Y,Z을 기준으로 최소로 이어질 수 있는 간선 N-1개 이외에 간선들은 MST를 만들 때 사용하지 않을 것을 알기에 미리 제외한 뒤에 union_find을 실행시키는 문제입니다.

1. 우선 x,y,z을 기준으로 정렬
2. x,y,z을 기준으로 정렬된 점들 끼리 서로 이어줍니다.
3. 이렇게 나온 간선들을 다시한번 정렬해줍니다.
4. 크루스칼 알고리즘을 통해 MST를 완성시켜줍니다.

1. 우선 x,y,z을 기준으로 정렬

for (int i = 0;i < N;i++)
{
	int _x, _y, _z = 0;
	cin >> _x >> _y >> _z;
	xg.push_back({ _x,i });
	yg.push_back({ _y,i });
	zg.push_back({ _z,i });
}

::sort(xg.begin(), xg.end());
::sort(yg.begin(), yg.end());
::sort(zg.begin(), zg.end());

2. x,y,z을 기준으로 정렬된 점들 끼리 서로 이어줍니다.

for (int i = 0;i < N - 1;i++)
{
	int _temp = abs(xg[i].first - xg[i + 1].first);
	-t.push_back(tie(_temp, xg[i].second, xg[i + 1].second));
	temp = abs(yg[i].first - yg[i + 1].first);
	t.push_back(tie(_temp, yg[i].second, yg[i + 1].second));
	_temp = abs(zg[i].first - zg[i + 1].first);
	t.push_back(tie(_temp, zg[i].second, zg[i + 1].second));
	}

3. 이렇게 나온 간선들을 다시한번 정렬해줍니다.

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

4. 크루스칼 알고리즘을 통해 MST를 완성시켜줍니다.

int result = 0;
int count = 0;

for (int i = 0;i < t.size();i++)
{
	int _cost, _i, _j = 0;
	tie(_cost, _i, _j) = t[i];

	if (union_find(_i, _j))
	{
		result += _cost;
		count++;
	}

	if (count == N - 1)
		break;
}

풀이

첫번째 풀이

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

vector<pair<int, int>>xg;
vector<pair<int, int>>yg;
vector<pair<int, int>>zg;

vector<tuple<int, int, int>>adj;
vector<tuple<int, int, int>>t;

vector<int>p(100'001, -1);

int find(int num)
{
	if (p[num] == -1)return num;
	return p[num] = find(p[num]);
}

bool union_find(int u, int v)
{
	u = find(u); v = find(v);
	if (u == v)return false;
	if (u > v)p[u] = v;
	else p[v] = u;
	return true;
}

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

	int N = 0;
	cin >> N;

	for (int i = 0;i < N;i++)
	{
		int _x, _y, _z = 0;
		cin >> _x >> _y >> _z;
		xg.push_back({ _x,i });
		yg.push_back({ _y,i });
		zg.push_back({ _z,i });
	}

	::sort(xg.begin(), xg.end());
	::sort(yg.begin(), yg.end());
	::sort(zg.begin(), zg.end());

	for (int i = 0;i < N - 1;i++)
	{
		int _temp = abs(xg[i].first - xg[i + 1].first);
		t.push_back(tie(_temp, xg[i].second, xg[i + 1].second));
		_temp = abs(yg[i].first - yg[i + 1].first);
		t.push_back(tie(_temp, yg[i].second, yg[i + 1].second));
		_temp = abs(zg[i].first - zg[i + 1].first);
		t.push_back(tie(_temp, zg[i].second, zg[i + 1].second));
	}

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

	int result = 0;
	int count = 0;

	for (int i = 0;i < t.size();i++)
	{
		int _cost, _i, _j = 0;
		tie(_cost, _i, _j) = t[i];

		if (union_find(_i, _j))
		{
			result += _cost;
			count++;
		}

		if (count == N - 1)
			break;
	}

	cout << result;

	return 0;
}