4386. 별자리 만들기

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

4386번: 별자리 만들기

 

문제 설명

N개의 별에 대한 (x, y) 좌표가 있다. 이 별들을 직선으로 이어 별자리를 만든다고 한다.

별자리를 만들 때는 다음 조건을 따른다. 

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다

선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

 

비용은 두 별 사이의 거리이고, 모든 별들을 선을 통해 하나로 만든다는 내용으로 보면 별이 node인 MST를 구성하라는 문제이다.

 

별이 node라면 간선은 두 별 사이에 선을 뜻한다.

모든 간선을 구하는 것은 모든 별에 대해 어떤 별과 다른 모든 별의 거리를 모두 구해 총 \( \frac{N(N+1)}{2} \) 개의 간선을 구축하면 된다.

 

MST 최소 비용은 크루스칼 알고리즘 또는 프림 알고리즘을 사용하여 구할 수 있다.

 

 

크루스칼 알고리즘을 사용한 방법으로 해결한 코드이다.

#include <bits/stdc++.h>
 
using namespace std;
 
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
 
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
double getDistance(pair<double, double> a, pair<double, double> b)
{
    return pow((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second), 0.5);
}
 
#define SIZE 101
class Disjoint_Set
{
public:
    int parent[SIZE+1];
    Disjoint_Set()
    {
        for(int i=1;i<=SIZE;i++)
            parent[i] = i;
    }
    int find(int v)
    {
        if(parent[v] == v) return v;
        return parent[v] = find(parent[v]);
    }
    bool merge(int u, int v)
    {
        u = find(u);
        v = find(v);
        if(u == v) return false;
        parent[u] = v;
        return true;
    }
};
 
Disjoint_Set DS;
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n;
    cin >> n;
    vector<pair<double, double>> points(n+1);
    for(int i=1;i<=n;i++)
    {
        cin >> points[i].first >> points[i].second;
    }
    vector<pair<double, pii>> dists;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            dists.push_back({getDistance(points[i], points[j]), {i, j}});
        }
    }
    sort(dists.begin(), dists.end());
    double ans = 0.0;
    for(size_t i=0;i<dists.size();i++)
    {
        if(DS.merge(dists[i].second.first, dists[i].second.second))
        {
            ans += dists[i].first;
        }
    }
    cout << ans;
 
    return 0;
}