BOJ 4386 - 별자리 만들기

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

 

접근

전형적인 최소 스패닝 트리 문제이다. 따라서 크루스칼을 이용하였다.

이번 문제는 별들 사이의 거리를 직접 점과 점 사이의 거리를 이용하여 구해야 한다.

그 외에는 쉽게 해결 가능하다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <string>

using namespace std;

int n;
typedef pair <double , pair<double, double >> p;
vector<p> edges;
vector<pair<int, int>> vertices;

int parent[101];

int find_parent(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find_parent(parent[x]);
}

void union_parent(int x, int y) {
    x = find_parent(x);
    y = find_parent(y);

    if (x < y) {
        parent[y] = x;
    }
    else {
        parent[x] = y;
    }
}

double kruskal() {
    int mst_cnt = 0;
    double sum = 0;

    for (int i = 0; i < edges.size(); i++) {
        p cur = edges[i];

        int from = cur.second.first;
        int to = cur.second.second;

        if (find_parent(from) == find_parent(to)) {
            continue;
        }

        mst_cnt++;
        sum += cur.first;
        union_parent(from, to);

    }
    return sum;
}

void calc_edges() {
    for (int i = 0; i < vertices.size(); i++) {
        for (int j = i + 1; j < vertices.size(); j++) {
            double x1 = vertices[i].first;
            double y1 = vertices[i].second;
            double x2 = vertices[j].first;
            double y2 = vertices[j].second;

            double dist = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));
            edges.push_back({ dist, {i,j} });
        }
    }
}

void init() {
    calc_edges();
    sort(edges.begin(), edges.end());

    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        double x, y;
        cin >> x >> y;
        vertices.push_back({x, y});
    }

    init();
    double res = kruskal();
    cout << res;

    return 0;
}