[C++] 별자리 만들기

solved ac 클래스 5를 따기 위해 클래스 풀던 중 풀어보게 된 문제

4386 별자리 만들기 이다

 

스패닝 트리 활용 문제로 좋은 것 같다

사실 처음에는 어떻게 풀어야 할 지 감이 잘 안와서 알고리즘 분류를 먼저 보았다

알고리즘 분류에 MST라고 나와있었고 그제서야 별의 개수가 매우 작아 모든 경우를 edge로 하여 MST를 만들면 되겠구나 하는 생각이 들었다

역시 input 크기 보기는 매우 중요하다

 

#include <stdio.h>
#include <queue>
#include <math.h>
using namespace std;
 
typedef pair<double,double> pdd;
typedef pair<int,int> pii;
typedef pair<double,pii> p;
 
pdd stars[101];
int par[101];
priority_queue<p> pq;
 
double dist(int i, int j){
    return (stars[i].first - stars[j].first)*(stars[i].first - stars[j].first) + (stars[i].second - stars[j].second)*(stars[i].second - stars[j].second);
}
 
int find(int x){
    if(par[x]==x) return x;
    else return par[x] = find(par[x]);
}
 
int main(){
    int N;
    scanf("%d",&N);
    for(int i = 1 ; i <= N ; i++){
        scanf("%lf %lf",&stars[i].first,&stars[i].second);
        par[i] = i;
    }
 
    for(int i = 1 ; i <= N ; i++){
        for(int j = i+1 ; j <= N ; j++){
            pq.push(make_pair(sqrt(dist(i,j))*-1,make_pair(i,j)));
        }
    }
    double ans = 0;
    while(!pq.empty()){
        p cur = pq.top();
        pq.pop();
        int x = cur.second.first;
        int y = cur.second.second;
        if(find(x)!=find(y)){
            ans += cur.first*-1;
            par[find(x)] = y;
        }
    }
    printf("%lf\n",ans);
}

 

코드는 길지 않다

모든 별들의 위치를 입력 받은 후 모든 edge를 우선순위큐에 넣어주었다

이 때 중복을 막기 위해 i,j에서 j가 i보다 큰 경우만 세었다

 

그 후에는 union find를 사용하는 크루스칼 알고리즘을 통해 MST를 만들었다

edge가 MST에 포함된다면 그 거리를 정답에 더해주었다