백준 4386번. 별자리 만들기(c++) / MST(kruskal)

모든 점을 연결하는 최소 비용을 구하는 문제이다.

따라서 MST알고리즘을 사용해야한다. 글쓴이는 그 중 kruskal 알고리즘을 사용하여 문제를 풀었다.

 

벡터에 {두 점을 연결하는 비용, {점1, 점2}}의 형태로 정보를 저장해주었다.

그리고 벡터를 비용순으로 sort한다.

모든 점을 하나씩 union하면서 최소 비용을 찾는다.

 

 

코드 첨부

// 별자리 만들기(MST->kruskal)
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
 
int n;
double x, y;
int connect[101] = {0, };
vector<pair<double, double>> stars;
vector<pair<double, pair<int, int>>> v;
double answer = 0;
 
int find(int a){
    if(a==connect[a]){
        return a;
    }
        
    return connect[a] = find(connect[a]);
}
 
double cal(double x1, double y1, double x2, double y2)
{
    return sqrt(pow(x2-x1, 2)+pow(y2-y1, 2));
}
 
int main()
{
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>x>>y;
        stars.push_back(make_pair(x, y));
    }
 
    // 두 점 사이의 거리를 저장한다.
    for(int i=0; i<stars.size(); i++){
        for(int j=i+1; j<stars.size(); j++){
            double cost = cal(stars[i].first, stars[i].second, stars[j].first, stars[j].second);
            v.push_back(make_pair(cost, make_pair(i, j)));
        }
    }
 
    for(int i=0; i<n; i++){
        connect[i] = i;
    }
 
    sort(v.begin(), v.end());
 
    for(int i=0; i<v.size(); i++){
        int x = v[i].second.first;
        int y = v[i].second.second;
        double cost = v[i].first;
 
        int a = find(x);
        int b = find(y);
 
        if(a!=b){
            connect[a] = b;
            answer += cost;
        }
    }
 
    cout.precision(3);
    cout<<answer<<"\n";
    return 0;
}

 

 

문제 첨부

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

4386번: 별자리 만들기