별자리 만들기 (feat. 백준, 4386번)

별자리 만들기
https://www.acmicpc.net/problem/4386

4386번: 별자리 만들기

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
struct Star{
    double x;
    double y;
};
Star stars[101];
int N;
vector<pair<int, double>> arr[101];
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> q;
bool visit[101];
double distance(const Star& v1, const Star& v2){
    return sqrt(pow(v2.x - v1.x, 2.0) + pow(v2.y - v1.y, 2.0));
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    cin >> N;
    memset(visit, false, N);
    double ans = 0, dist;
    for(register int n = 1; n <= N; ++n)
        cin >> stars[n].x >> stars[n].y;
    for(register int i = 1, j; i <= N - 1; ++i)
        for(j = i + 1; j <= N; ++j){
            dist = distance(stars[i], stars[j]);
            arr[i].push_back(make_pair(j, dist)), arr[j].push_back(make_pair(i, dist));
        }
    q.push(make_pair(0.0, 1));
    while(!q.empty()){
        dist = q.top().first;
        int next = q.top().second;
        q.pop();
        if(visit[next])
            continue;
        visit[next] = true;
        ans += dist;
        for(auto& v : arr[next]){
            int nnext = v.first;
            dist = v.second;
            q.push(make_pair(dist, nnext));
        }
    }
    printf("%.2f", ans);
	return 0;
}
// *&)*@*

 

반응형

최소 스패닝 트리를 생성하는 문제입니다.

저는 프림 알고리즘을 사용하여 풀이하였습니다.

각 별의 정보가 있으므로 1-2, 1-3, 1-4, ... 1-N, 2-3, 2-4, ..., 2-N 과 같이 별들을 이어줄때 비용을 모두 구한 뒤, 비용이 가장 저렴한 순서대로 이어주면 되겠습니다.