[백준 알고리즘] 4386번: 별자리 만들기
May 16, 2020
https://www.acmicpc.net/problem/4386
문제
문제
도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.
별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다. 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. 별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.
입력
첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)
둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.
출력
첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.
풀이
크루스칼 알고리즘을 사용해서 해결할 수 있는 문제였다. 크루스칼 알고리즘 자체를 적용하는 것은 어렵지 않았지만, 간선정보가 직접적으로 주어지지 않고 좌표로 주어지기 때문에 좌표와 간선은 컨테이너에 어떻게 보관할지 생각하는 것이 쉽지 않았다. 어차피 한 별에 대해서 다른 별들과 다 이어봐야 가장 짧은 거리를 알 수 있기 때문에 일단 좌표들을 다 입력받고, 가지고 있는 좌표들을 다른 모든 좌표들과 맵핑시켜서 간선정보를 구하는 방법을 사용했다. 처음에는 이렇게 하려면 브루트포스로 간선을 구해야되는데 괜찮나? 싶었지만 별의 갯수가 최대 100개이기 때문에 괜찮았던 것 같다.
갈수록 알고리즘이 알려워진다.. 열심히하자!
코드
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int parent[101];
int level[101];
vector<pair<double, double>> stars;
vector<pair<double, pair<int, int>>> edges ; // <간선길이, <출발점, 도착점>>
double calcDist(double x1, double y1, double x2, double y2){
return sqrt(pow(x2-x1, 2) + pow(y2-y1, 2));
}
int find (int a){
if (a == parent[a]) return a;
return parent[a] = find(parent[a]);
}
bool merge (int a, int b){
a = find(a);
b = find(b);
if (a == b) return false;
if(level[a] > level[b]) parent[a] = b;
else parent[b] = a;
if (level[a] == level[b]) level[a]++;
return true;
}
int main (){
int n;
scanf("%d", &n);
int v = n;
/* get position of stars */
while(n--){
double x, y;
scanf("%lf %lf", &x, &y);
stars.push_back({x, y});
}
/* build graph by getting edges for all stars */
for (int i = 0 ; i < stars.size() ;i++){
for (int j = i+1 ; j < stars.size() ; j++){
edges.push_back({calcDist(stars[i].first, stars[i].second, stars[j].first, stars[j].second), {i, j}});
}
}
/* intialize parent array for union-find */
for (int i = 0 ; i < v ; i++){
parent[i] = i;
}
/* sort edges by their weights for greedy approach */
sort(edges.begin(), edges.end());
double ret = 0;
for (int i = 0 ; i < edges.size() ; i++){
/* add all min-weight edges that does not make cycle */
if(merge(edges[i].second.first, edges[i].second.second)){
ret += edges[i].first;
}
}
printf("%0.2f", ret);
}
