백준[4386] 별자리 만들기

문제 설명

풀이 방법

최소 신장 트리(MST)를 구하는 문제이다. MST는 prim 알고리즘과 kruskal 알고리즘을 통해 구할 수 있다.

이 풀이는 prim 알고리즘을 이용했다.

cf) prim 알고리즘을 모른다면 여기를 참고하세요

코드

#include <cstdio>
#include <cmath>
#include <queue>

using namespace std;
using pdd = pair<double, double>;
using pdi = pair<double, int>;

pdd arr[102];
bool visited[102];
priority_queue<pdi, vector<pdi>, greater<pdi>> pq; // 최소 힙
int N;
double ans;

//점과 점 사이의 거리
double dist(pdd a, pdd b) {
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}

void prim(int s) {
    visited[s] = true;
    for (int i = 0; i < N; i++) {
        if (!visited[i]) pq.push({dist(arr[s], arr[i]), i});
    }
    while (!pq.empty()) {
        auto [x, y] = pq.top();
        pq.pop();
        if (!visited[y]) {
            ans += x;
            prim(y);
            return;
        }
    }
}

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) scanf("%lf %lf", &arr[i].first, &arr[i].second);
    prim(0);
    printf("%.2lf", ans);
}

문제 링크 : https://www.acmicpc.net/problem/4386