[백준] 4386번 : 별자리 만들기 (C++)

4386번 : 별자리 만들기

---

문제 )

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

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

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

 

 

입력 :

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

 

 

 

출력 :

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

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
 
using namespace std;
 
// class를 이용한 간선 관리
class Edge
{
public:
    int node[2];
    double distance;
 
    Edge(int a, int b, double c)
        :node{ a, b }, distance(c)
    {}
 
    bool operator < (Edge& edge)
    {
        return this->distance < edge.distance;
    }
};
 
int par[110];
int rank[110];
vector<vector<double>> temp;
vector<Edge> vec;
 
int find(int x)
{
    if (par[x] == x)
    {
        return x;
    }
    else
    {    // 경로압축
        par[x] = find(par[x]);
        return par[x];
    }
}
 
void union_(int a, int b)
{
    a = find(a);
    b = find(b);
 
    // union by rank
    if (::rank[a] < ::rank[b])
    {
        par[a] = b;
    }
    else if (::rank[a] > ::rank[b])
    {
        par[b] = a;
    }
    else
    {
        par[a] = b;
        ::rank[a]++;
    }
}
 
int main()
{
    // 입출력 속도 향상
    cin.tie(0);
    ios_base::sync_with_stdio(false);
 
    // 기본 부모노드 초기화
    for (int i = 0; i < 110; i++) par[i] = i;
 
    int n;
    cin >> n;
 
    // 좌표 입력 받기
    double a, b;
    for (int i = 0; i < n; i++)
    {
        cin >> a >> b;
        temp.push_back(vector<double>{a, b});
    }
 
    // 입력받은 좌표 활용, 좌표들이 가질 수 있는 모든 거리 계산
    // 별의 개수는 100개 이하이므로, 최대 10000개 (시간 제한 여유)
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            a = abs(temp[i][0] - temp[j][0]);
            b = abs(temp[i][1] - temp[j][1]);
            double dist = pow(pow(a, 2) + pow(b, 2), 0.5);
            vec.push_back(Edge(i + 1, j + 1, dist));
        }
    }
 
    // 최소비용이므로 오름차순으로 정렬
    sort(vec.begin(), vec.end());
 
    double cost = 0;
    // 최소 비용순서대로 별자리를 이어준다. (크루스칼 알고리즘)
    for (auto i = vec.begin(); i < vec.end(); i++)
    {
        int temp1 = i->node[0];
        int temp2 = i->node[1];
 
        if (find(temp1) != find(temp2))
        {
            union_(temp1, temp2);
            cost += i->distance;
        }
    }
 
    // 소수점 둘째자리까지 출력 고정
    cout << fixed;
    cout.precision(2);
    cout << cost;
    
    return 0;
}
 

 

---

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

4386번: 별자리 만들기