백준/1774/MST/우주신과의 교감

백준/1774/MST/우주신과의 교감

문제 해석

우주신과의 교감을 위해서 모든 정점을 연결하는 그래프를 만들면서 이 간선의 비용을 최소로하는 minimun spanning tree 문제입니다.

문제 풀이

1. 모든 정점의 2차원 좌표값을 순서대로 입력받는다.
2. 이미 연결된 정점은 union 해주어 이미 연결되어 있는 간선으로 취급한다.
3. 이 후에 입력받은 정점을 활용해 임의의 선들을 만들어준다.(n(n-1)개의 간선)
4. 임의의 선들을 크기별로 정렬하고 union을 통해 선별해준다.
5. 값을 출력한다.

1. 모든 정점의 2차원 좌표값을 순서대로 입력받는다.

for (int i = 0;i < N;i++)
{
	double X, Y = 0;
	cin >> X >> Y;
	v.push_back(make_pair(X, Y)); // input to vector
}

2. 이미 연결된 정점은 union 해주어 이미 연결되어 있는 간선으로 취급한다.

for (int i = 0;i < M;i++)
{
	int X, Y = 0;
	cin >> X >> Y;
	union_find(X - 1, Y - 1);
}

3. 이 후에 입력받은 정점을 활용해 임의의 선들을 만들어준다.(n(n - 1)개의 간선)

int _count = 0;
for (int i = 0;i < N;i++)
{
	for (int j = i + 1;j < N;j++)
	{
		double cost = sqrt(pow(v[i].first - v[j].first, 2) + pow(v[i].second - v[j].second, 2));
		t[_count] = tie(cost, i, j);
		_count++;
	}
}

4. 임의의 선들을 크기별로 정렬하고 union을 통해 선별해준다.

sort(t, t + _count);

double result = 0.f;
for (int i = 0;i < _count;i++)
{
	double cost = 0.f;
	int st = 0;
	int en = 0;
	tie(cost, st, en) = t[i];

	if (union_find(st, en))
	{
		result += cost;
	}
}

5. 값을 출력한다.

printf("%.2f", result);

풀이

첫번째 풀이(입력 값 중 이미 연결된 그룹 오류 및 출력 형식 오류)

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

vector<pair<float, float>>v;

vector<int>p(1001, -1);

tuple<int, int, int>t[1'000'001];

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()
{
	int N, M = 0;

	cin >> N >> M;
	for (int i = 0;i < N;i++)
	{
		int X, Y = 0;
		cin >> X >> Y;
		v.push_back(make_pair(X, Y));
	}

	int X, Y = 0;
	cin >> X >> Y;
	union_find(X - 1, Y - 1);
	

	int _count = 0;
	for (int i = 0;i < N;i++)
	{
		for (int j = i + 1;j < N;j++)
		{
			float cost = sqrt(pow(v[i].first - v[j].first, 2) + pow(v[i].second - v[j].second, 2));
			t[_count] = tie(cost, i, j);
			_count++;
		}
	}

	sort(t, t + _count);

	float result = 0.f;
	for (int i = 0;i < _count;i++)
	{
		float cost = 0.f;
		int st = 0;
		int en = 0;
		tie(cost, st, en) = t[i];

		if (union_find(st, en))
		{
			result += cost;
		}
	}

	cout<<result;


	return 0;
}

두번째 풀이(출력 값 데이터 형식 오류)

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

vector<pair<float, float>>v;

vector<int>p(1001, -1);

tuple<float, int, int>t[1'000'001];

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()
{
	int N, M = 0;

	cin >> N >> M;
	for (int i = 0;i < N;i++)
	{
		float X, Y = 0;
		cin >> X >> Y;
		v.push_back(make_pair(X, Y));
	}

	for (int i = 0;i < M;i++)
	{
		int X, Y = 0;
		cin >> X >> Y;
		union_find(X - 1, Y - 1);
	}

	int _count = 0;
	for (int i = 0;i < N;i++)
	{
		for (int j = i + 1;j < N;j++)
		{
			float cost = sqrt(pow(v[i].first - v[j].first, 2) + pow(v[i].second - v[j].second, 2));
			t[_count] = tie(cost, i, j);
			_count++;
		}
	}

	sort(t, t + _count);

	double result = 0.f;
	for (int i = 0;i < _count;i++)
	{
		float cost = 0.f;
		int st = 0;
		int en = 0;
		tie(cost, st, en) = t[i];

		if (union_find(st, en))
		{
			result += cost;
		}
	}

	printf("%.2f", result);


	return 0;
}

세번째 풀이

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

vector<pair<double, double>>v;

vector<int>p(1001, -1);

tuple<double, int, int>t[1'000'001];

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()
{
	int N, M = 0;

	cin >> N >> M;
	for (int i = 0;i < N;i++)
	{
		double X, Y = 0;
		cin >> X >> Y;
		v.push_back(make_pair(X, Y));
	}

	for (int i = 0;i < M;i++)
	{
		int X, Y = 0;
		cin >> X >> Y;
		union_find(X - 1, Y - 1);
	}

	int _count = 0;
	for (int i = 0;i < N;i++)
	{
		for (int j = i + 1;j < N;j++)
		{
			double cost = sqrt(pow(v[i].first - v[j].first, 2) + pow(v[i].second - v[j].second, 2));
			t[_count] = tie(cost, i, j);
			_count++;
		}
	}

	sort(t, t + _count);

	double result = 0.f;
	for (int i = 0;i < _count;i++)
	{
		double cost = 0.f;
		int st = 0;
		int en = 0;
		tie(cost, st, en) = t[i];

		if (union_find(st, en))
		{
			result += cost;
		}
	}

	printf("%.2f", result);


	return 0;
}