백준 BOJ 4386 별자리 만들기

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

4386번: 별자리 만들기

문제 해설

n개의 별(1<= N <= 100)이 주어질 때,

모든 별을 이어 별들을 잇는 선의 길이가 최소인 별자리를 만들고, 그 길이를 구하려 한다.

 

n이 100이하이므로, 주어진 별을 모두 짝지어 거리를 계산해도 10,000번 밖에 안 걸린다.

Prim 알고리즘을 떠올려보자

0) 임의의 별을 선택하고 별자리에 포함시킨다.

1) 현재 선택된 별(now)로부터 아직 선택되지 않은 별(next)로 나가는 간선 중 길이가 최소인 간선을 선택한다.

2) 새로 선택된 별(next)을 별자리에 포함시킨다.

3) 새로 선택된 별(next)을 현재 선택된 별(now)로 두고, 모든 별이 별자리에 포함될 때까지 1-2를 반복한다.

 

위의 알고리즘을 따라가면, 길이가 최소인 별자리에 포함될 간선들을 구할 수 있다.

별자리의 길이를 출력하는 것이 목표이므로 1)에서 간선을 선택할 때 간선의 길이를 누적시키면 된다. 

 

#include <iostream>
#define fio cin.tie(0)->sync_with_stdio(0)
using namespace std;

#include <queue>
#include <cmath>
#include <vector>
int N;
bool visited[100];
vector<pair<double, int> > distance_from[100];

//두 별 사이의 거리를 반환
double get_dist(const pair<double, double>& A, const pair<double, double>& B){
	double x_ = A.first - B.first;
	x_ *= x_;
	double y_ = A.second - B.second;
	y_ *= y_;
	return sqrt(x_ + y_);
}
int main() {
	fio;
	cin >> N;
	vector<pair<double, double> >point(N);
	for(int i=0; i <N; i++){
		double x, y; cin >> point[i].first >> point[i].second;
	}
	//별들 사이의 거리 계산해두기
	for(int i=0; i<N; i++){
		for(int j=i+1; j<N; j++){
			double distance = get_dist(point[i], point[j]);
			distance_from[i].push_back(make_pair(distance, j));
			distance_from[j].push_back(make_pair(distance, i));
		}
	}
	
	double total_length = 0;
	priority_queue<pair<double, int> > pq;
	pq.push(make_pair(0, 0)); // 0번 별 넣기
	while(!pq.empty()){
		pair<double, int> now = pq.top(); pq.pop();
		if(visited[now.second]) continue;
		visited[now.second] = true;
		total_length += -now.first;
		for(int i=0; i<distance_from[now.second].size(); i++){
			double next_dist = distance_from[now.second][i].first;
			int next_star = distance_from[now.second][i].second;
			//이미 이은 별
			if(visited[next_star]) continue;
			pq.push(make_pair(-next_dist, next_star));
		}
	}
	cout << total_length;
	return 0;
}