[백준 1774] 우주신과의 교감 (C++)

이 문제는 모든 정점을 연결할 때 필요한 최소 통로 길이를 구하는 문제이다. 즉, 최소 비용으로 모든 정점을 연결해야하는 문제이므로 MST로 접근해야한다.

간단하게 Union-Find 알고리즘과 크루스칼 알고리즘으로 문제를 해결해보자.

이 문제에서, $M$개의 간선이 이미 연결된 상태이므로 이를 반영하기 위해서, 해당 정점끼리는 서로 연결된 그룸이라는 의미로 merge(x, y)연산을 수행한다.

이후, 모든 간선 정보를 vector<tuple<ll, int, int>> edge에 저장한다. 원소는 {비용, 시점, 종점}의 형태로하며, $(x_1, y_1)$과 $(x_2, y_2)$인 두 정점이 주어졌을 때, 비용은 $(x_1 - x_2)^2 + (y_1 - y_2)^2$으로 거리의 제곱이라 하자. 이유인 즉슨, 출력시 소수점 아래 두자리까지만 출력해야 하는데, double로 연산을 반복해나가면 오차가 발생할 여지가 있기 때문에, 간선 정보에서는 거리의 제곱을 저장하도록 했다.

이후, 간선들을 정렬하고 정점들이 같은 그룹이 아니면, 해당 간선을 선택하면 된다. 즉, ans값을 증가시키고, 같은 그룹으로 표시하면 된다.

이를 코드로 옮기면 다음과 같다.

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
using ll = long long;

int n, m, cnt;
pair<int, int> coord[1001];
vector<int> p(1001, -1);
vector<tuple<ll, int, int>> edge; // {비용, 정점1, 정점2}
double ans;

int find(int x) {
	if (p[x] < 0) return x;
	return p[x] = find(p[x]);
}

void merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return;
	p[y] = x;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed;
	cout.precision(2);

	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> coord[i].X >> coord[i].Y;
	for (int i = 0, x, y; i < m; i++) {
		cin >> x >> y;
		if (find(x) == find(y)) continue;
		merge(x, y);
		cnt++;
	}

	ll square;
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			ll dx = coord[i].X - coord[j].X, dy = coord[i].Y - coord[j].Y;
			ll square = dx * dx + dy * dy;
			edge.push_back({square, i, j});
		}
	}

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

	for (int i = 0; i < edge.size(); i++) {
		int x, y;
		tie(square, x, y) = edge[i];
		if (find(x) == find(y)) continue;
		merge(x, y);
		ans += sqrt(square);
		cnt++;
		if (cnt == n - 1) break;
	}
	cout << ans;
}