별자리 만들기 - 4386번 백준

문제

문제 난이도 : 골드 3

문제 분류 : 최소 스패닝 트리(Minimum Spanning Tree)

문제 리뷰

약간의 기하(초등)와 MST가 합쳐진 문제다.

double 자료형에 precision을 소수점 두자리까지 출력해야해서 골드 3으로 책정된 듯 하다.

 

문제 소스코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <memory.h>

using namespace std;
vector<vector<double>> Edges;
int Root[1001];

int n;
void Init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    std::cout.tie(NULL);
}

int Find(int x) {
    if (Root[x] == x) {
        return x;
    }
    else {
        return Root[x] = Find(Root[x]);
    }
}
void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x != y) {
        Root[x] = y;
    }
}
vector<vector<double>> Kruskal() {
    vector<vector<double>> MST;
    for (int i = 0; i < Edges.size(); i++) {
        vector<double> tmp = Edges[i];
        if (Find(tmp[1]) == Find(tmp[2])) continue;
        MST.push_back(tmp);
        if (MST.size() == n - 1) return MST;
        Union(tmp[1], tmp[2]);
    }

}

int main()
{
    //Initialize
    Init();
    cin >> n;
    for (int i = 0; i < 1001; i++) {
        Root[i] = i;
    }
    vector<pair<double, double>> StarPoint;
    for (int i = 0; i < n; ++i) {
        float x, y;
        cin >> x >> y;
        StarPoint.push_back({ x,y });
    }

    for (int i = 0; i < StarPoint.size(); i++) {
        for (int j = 0; j < StarPoint.size(); j++) {
            if (i != j) {
                Edges.push_back({ sqrt(pow(StarPoint[i].first - StarPoint[j].first ,2)
                    + pow(StarPoint[i].second - StarPoint[j].second ,2)) , double(i), double(j)});
            }
        }
    }
    sort(Edges.begin(), Edges.end(), less<vector<double>>());
    double Length = 0;
    vector<vector<double>> tmp = Kruskal();
    for (vector<double> v : tmp) {
        Length += v[0];
    }
    cout.precision(3);
    cout << Length;
}