백준 4386번 : 별자리 만들기 - 최소스패닝트리, 크루스칼

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

4386번: 별자리 만들기

1. 문제 설명

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며,
최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

 

 

별이 n개 주어지고 별들의 각각 좌표가 주어진다.

 

모든 별을 이용해서 최소 거리, 비용으로 별자리를 만들어야한다.

 

 

2. 접근 방법[알고리즘]

최소 비용으로 모든 별을 이어야 하므로 최소스패닝트리, 최소 신장 트리(MST)를 만들어야한다.

 

크루스칼 알고리즘이나 프림 알고리즘을 사용해서 만들면 된다.

 

나는 크루스칼 알고리즘을 이용했다.

 

 

 

 

3. 문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int unf[10001];

struct Edge{
	int v1;
	int v2;
	double val;
	Edge(int a, int b, double c){
		v1=a;
		v2=b;
		val=c;
	}
	bool operator<(const Edge &b) const{
		return val>b.val;
	}
};

int Find(int v){
	if(v==unf[v]) return v;
	else return unf[v]=Find(unf[v]);
}

void Union(int a, int b){
	a=Find(a);
	b=Find(b);
	if(a!=b) unf[a] = b;
}

double dist(pair<double, double> &a , pair<double, double> &b){
	return sqrt(pow(a.first-b.first,2) + pow(a.second - b.second,2));
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	priority_queue<Edge> Q;
	double res=0;
	int n;
	vector<pair<double, double> > star;
	
	cin >> n;
	for(int i=0; i<n; i++){
		double x,y;
		cin >> x >> y;
		star.push_back(make_pair(x,y));
	}
	
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			Q.push(Edge(i,j, dist(star[i],star[j])));
		}
	}
	
	for(int i=0; i<n; i++){
		unf[i] = i;
	}
	
	
	while(!Q.empty()){
		int node_a = Q.top().v1;
		int node_b = Q.top().v2;
		double d = Q.top().val;
		Q.pop();
		
		if(Find(node_a)!=Find(node_b)){
			Union(node_a, node_b);
			res += d;
		}		
	}
	cout << fixed;
	cout.precision(3);
	cout << res ;
	
	
}

문제에서 출력을 절대/상대 오차 10-2까지 허용한다고 해서

 

아예 소수 세번째 자리까지 출력했다.

 

출력과정에서 반올림이 될 수도 있다고 생각해서 널널하게 세번째까지 출력했다.

 

input을 star에 입력해주었다.

 

그리고 모든 star 요소에 대해서 각 거리를 구해 우선순위 큐(최소힙)에 넣고

 

두 별 사이의 거리가 최소인 Edge를 최소힙에서 꺼내서 Union&Find 알고리즘을 이용하여

 

이미 두 별이 연결되어 있으면 넘어가고, 연결되어 있지 않으면 연결해주고

 

그 두 별 사이의 거리를 res 변수에 더해주었다.

 

최소스패닝트리를 구하는 걸 연습하기 좋은 문제다.