BOJ: 별자리 만들기(4386) [C++]

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

 

문제

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

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

별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

 

 

MST를 구하는 문제

점의 좌표가 주어지므로 두 점 사이의 거리 공식을 이용해 edge 배열을 구해줘야 한다는 것이 포인트

마찬가지로 크루스칼 알고리즘을 사용하였다.

c++에서 소수점 출력 시, cout << fixed로 고정된 소수점 자리를 출력하게 할 수 있고 cout.precision(n)으로 소수점 n째자리로 정확도를 설정할 수 있다.

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

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

using namespace std;

typedef tuple<double, int, int>tp;
typedef pair<double, double>ci;
vector<int> parent;

int findParent(int x){
    if(parent[x]<0) return x;
    return parent[x] = findParent(parent[x]);
}

bool unionInput(int x, int y){
    int xp = findParent(x);
    int yp = findParent(y);
    if(xp==yp) return false;
    if(parent[xp]<parent[yp]) swap(xp, yp);
    parent[yp] += parent[xp];
    parent[xp] = yp;
    return true;
}

double kruskal(int n, vector<tp>&edge){
    double sum=0;
    int cnt=0;
    for(auto[w, n1, n2]: edge){
        if(!unionInput(n1,n2)) continue;
        sum += w;
        cnt++;
        if(cnt==n-1) return sum;
    }
    return sum;
}

int main()
{
    int n;
    double x,y;
    
    cin >> n;
    parent.assign(n+1, -1);
    vector<tp> edge;
    vector<ci> node;
    
    for(int i=0;i<n;i++){
        cin >> x >> y; //현재 점의 좌표
        node.push_back({x, y});
        //임의의 두 점에 대한 거리를 edge에 모두 저장
        //루트 ((x변화량)^2 + (y변화량)^2)
        for(int j=0;j<i;j++){
            double dx = x - node[j].first; //x변화량
            double dy = y - node[j].second; //y변화량
            double dist = sqrt(dx*dx + dy*dy);
            edge.push_back({dist, i, j});
        }
    }
    
    sort(edge.begin(), edge.end());
    double ans = kruskal(n, edge);
    
    cout << fixed;
    cout.precision(2);
    cout << ans;
    
    return 0;
}