백준 Gold 3 우주신과의 교감

우주신과의 교감 (백준 Gold 3)

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

주어지는 N개의 좌표들과
이미 건설된 M개의 연결점을 이용하여
모든 N개의 좌표들이 연결되기 위한 최소 비용을 구하는 문제

• 각 좌표값에 대한 계산은
  피타고라스로 계산
  

• 출력은 소수점 2자릿수 까지
  

풀이 방법

이전에도 풀었던 MST 계열의 문제이나
처음에 ‘이미 연결된’ 정보가 주어진다

• 이미 연결된 정보는 미리 ‘합쳐놓음’
  (Union)
  

• 이후 각 좌표들에 대한 Edge를 만들고
  비용 순 정렬
  

• 이후, Union 하며 비용 계산
  

제출 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include <iomanip>

using namespace std;

int FindParent(vector<int>& pv, int x)
{
	if (pv[x] == x)
		return x;

	return pv[x] = FindParent(pv, pv[x]);
}

bool Union(vector<int>& pv, int a, int b)
{
	a = FindParent(pv, a);
	b = FindParent(pv, b);

	if (a == b)
		return false;

	pv[a] = b;
	return true;
}

struct Star
{
	int y, x;
};

struct Edge
{
	int sIdx;
	int tIdx;
	long double cost;
};

long double GetDis(Star& a, Star& b)
{
	return sqrt(double(a.y - b.y) * (a.y - b.y) + double(a.x - b.x) * (a.x - b.x));
}

int main()
{
	int n, m;
	cin >> n >> m;

	cout << fixed << setprecision(2);

	vector<int> pv(n);
	for (int i = 0; i < n; i++)
		pv[i] = i;

	vector<Star> starV(n);

	for (int i = 0; i < n; i++)
	{
		cin >> starV[i].x >> starV[i].y;
	}

	for (int i = 0; i < m; i++)
	{
		int t1, t2;
		cin >> t1 >> t2;
		t1--;
		t2--;
		Union(pv, t1, t2);
	}

	vector<Edge> ev;

	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			ev.push_back({ i,j,GetDis(starV[i],starV[j]) });
		}
	}

	sort(ev.begin(), ev.end(), [](const auto& a, const auto& b) {return a.cost < b.cost; });

	long double ans = 0.0;

	for (const auto& e : ev)
	{
		if (Union(pv,e.sIdx, e.tIdx))
		{
			ans += e.cost;
		}
	}

	cout << ans;

	return 0;
}

결과