백준 4386 별자리 만들기 (C++)

4386번: 별자리 만들기

크루스칼 알고리즘을 이용한 문제이다. 먼저 입력받은 별들 간의 거리를 모두 구해 벡터에 저장해주고 거리를 기준으로 오름차순으로 졍렬을 해주었다. 그리고 크루스칼을 통해 루트를 바꿔주게 되는데 거리 순으로 정렬을 했으므로 가까운 거리부터 루트를 지정해주게 되므로 결과적으로 최소 비용이 나오게 된다. 루트를 바꾸는 과정의 비용을 모두 더해 출력해주었다. 생각보다 오래 걸린 문제였다. 크루스칼 알고리즘에 대해 기억해두자.

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

using namespace std;

int n;
double result = 0;
vector<pair<double, double>> A;
int root[100];
vector<pair<double, pair<double, double>>> v;

int findRoot(int a) {
    if (root[a] == a) return a;
    else return root[a] = findRoot(root[a]);
}

void unionRoot(int a, int b) {
    a = findRoot(a);
    b = findRoot(b);

    if (a != b) root[b] = a;
}

double dist(double x1, double y1, double x2, double y2) {
    return sqrt(pow((x1 - x2), 2) + pow((y1 - y2), 2));
}

void solution() {
    for (int i = 0; i < n; i++) {
        root[i] = i;
    }

    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            v.push_back({ dist(A[i].first,A[i].second,A[j].first,A[j].second),{i,j} });
        }
    }

    sort(v.begin(), v.end());

    for (int i = 0; i < v.size(); i++) {
        double cost = v[i].first;
        int a = v[i].second.first;
        int b = v[i].second.second;

        if (findRoot(a) != findRoot(b)) {
            unionRoot(a, b);
            result += cost;
        }
    }

    cout << fixed;
    cout.precision(2);
    cout << result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;

    double a, b;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        A.push_back({ a,b });
    }

    solution();

    return 0;
}