[백준] 4386번 별자리 만들기

4386 별자리 만들기

문제

---

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

-별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.

-모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

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

입력

---

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

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

출력

---

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

---

풀이)

모든 별들은 이어져 있어야 하며, 별들을 이을 때 최소 비용을 구하는 문제이므로 MST를 구현하면 되는 문제다.

MST는 Kruskal algorithm을 이용해서 구현했다.

과정

1. 별들의 좌표들을 모두 저장해둔다.

2. 저장해둔 별들의 위치를 이용해, 각 별마다 다른 별들과의 거리를 저장해둔다.

   거리 공식: 

   공식구하기 쉽게 <cmath>라이브러리를 이용한다.

   제곱근 함수는 sqrt(x) : x의 제곱근을 return

   제곱함수는 pow(x,y) : x^y를 return

3. 별들끼리의 거리를 저장한 배열을 거리 비용을 기준으로 오름차순으로 정렬한다.

4. 가장 비용이 적은 거리부터 하나씩 살펴보며 별들을 이어준다.

   (별들이 이미 이어졌는지는 Union-find를 이용해 확인해주면 된다.)

코드)

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
 
int n;
int parent[101];
int s[101];
 
struct Edge {
    int v1, v2;
    double dist;
    Edge(int v1, int v2, double dist) {
        this->v1 = v1;
        this->v2 = v2;
        this->dist = dist;
    }
    bool operator < (const Edge &a) {
        return dist < a.dist;
    }
};
vector<pair<double, double>> star;
vector<Edge> e;
 
int Find(int a) {
    if (a == parent[a]) return a;
    return parent[a] = Find(parent[a]);
}
int main() {
    
    scanf("%d", &n);
 
    double a, b;
    for (int i = 0; i < n; i++) {
        scanf("%lf %lf", &a, &b);
        star.push_back({ a,b });
        parent[i] = i;
        s[i] = 1;
    }
    for (int i = 0; i < star.size(); i++) {
        for (int j = i+1; j < star.size(); j++) {
            double x = star[i].first - star[j].first;
            double y = star[i].second - star[j].second;
            double diff = (double)sqrt((double)pow(x, 2) + (double)pow(y, 2));
            e.push_back({ i,j,diff });
        }
    }
    double result = 0;
    sort(e.begin(), e.end());
    for (int i = 0; i < e.size(); i++) {
        int v1 = Find(e[i].v1);
        int v2 = Find(e[i].v2);
        if (v1 == v2) continue;
        if (s[v1] < s[v2]) swap(v1, v2);
        parent[v2] = v1;
        s[v1] += s[v2];
        result += e[i].dist;
    }
    printf("%.2lf", result);
    return 0;
}