[BOJ 1774 // C++] 우주신과의 교감

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1774번 문제인 우주신과의 교감이다.
문제는 아래 링크를 확인하자.

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

1774번: 우주신과의 교감

전체 노드가 1000개 이하이므로 모든 가능한 에지의 수는 100만개 이하이다.

 

완전그래프를 만들고 이미 이어진 부분들을 처리한 후 그래프의 남은 부분에서 MST를 만들어 문제를 해결하자.

 

글쓴이는 kruskal 알고리즘을 이용했다. 이 때 각 에지의 길이를 이용해 우선순위를 매길 때, 각 변의 길이를 제곱근을 씌우기 전 정수의 형태로 저장해 실수오차의 위험성을 줄였다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
typedef long long ll;

int uf[1001];
int findf(int x) {
	if (x == uf[x]) return x;
	return uf[x] = findf(uf[x]);
}

int N, M;
ll X[1001], Y[1001];
priority_queue<pair<ll, pair<int,int>>> pq; // {-거리제곱, 연결된 두 노드}

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++) uf[i] = i;
	for (int i = 1; i <= N; i++) cin >> X[i] >> Y[i];
	for (int i = 1; i <= N; i++) {
		for (int j = i + 1; j <= N; j++) {
			pq.push(make_pair(-((X[j] - X[i]) * (X[j] - X[i]) + (Y[j] - Y[i]) * (Y[j] - Y[i])), make_pair(i, j)));
		}
	}

	while (M--) {
		int x, y; cin >> x >> y;
		x = findf(x), y = findf(y);
		uf[y] = x;
	}

	double ans = 0;
	while (!pq.empty()) {
		int x = pq.top().second.first, y = pq.top().second.second; double dist = sqrt(-pq.top().first);
		pq.pop();
		x = findf(x), y = findf(y);
		if (x != y) {
			ans += dist;
			uf[y] = x;
		}
	}

	cout << ans;
}