BOJ 1774 우주신과의 교감

사용한 알고리즘

알고리즘 설명

Union-find를 이용하여 입력되는 미리 연결되어 있는 다리를 연결시킨다.
이 뒤에 행성 간에 만들 수 있는 edge를 생성한다.
이 edge를 거리가 짧은 순으로 오름차순 한 뒤에 MST알고리즘을 적용한다.
edge를 앞에서 부터 하나씩 확인하며 연결할 필요가 없는 경우는 다리를 생성하지 않고, 연결이 필요한 경우 두 행성을 union-find로 연결시키고 필요한 다리 길이를 결과에 추가한다.

풀이

// baekjoon 1774 yechan
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;

#define SQ(x) ((x)*(x))
const int MAX_N=1001;

typedef pair<double, double> P;

int N, M, root[MAX_N];
P star[MAX_N];

// 두 행성 간에 거리
inline double dist(P &A, P &B) {
	return sqrt(SQ(A.first-B.first)+SQ(A.second-B.second));
}

// union-find 알고리즘
int find(int x) {
	if (!root[x]) return x;
	return root[x]=find(root[x]);
}

bool merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return false;
	root[b] = a;
	return true;
}

int main() {
	scanf("%d%d", &N, &M);
	for (int i=1; i<=N; i++)
		scanf("%lf %lf", &star[i].first, &star[i].second);

// 이미 연결되어 있는 행성
	while (M--) {
		int a, b;
		scanf("%d%d", &a, &b);
		merge(a,b);
	}

	vector<pair<double,pair<int,int> > > edge;

// 행성간 생성가능한 다리를 모두 저장
	for (int i=1; i<N; i++) {
		for (int j=i+1; j<=N; j++) {
			edge.push_back(make_pair(dist(star[i],star[j]), make_pair(i, j)));
		}
	}

// 길이가 작은 다리 순서로 정렬
	sort(edge.begin(), edge.end());

// MST 알고리즘 적용
	double ret = 0;
	for (int i=0; i<edge.size(); i++) {
		double w = edge[i].first;
		int x = edge[i].second.first;
		int y = edge[i].second.second;
		if (merge(x, y)) {
			ret += w;
		}
	}
	printf("%.2lf\n", ret);
	return 0;
}