[ BOJ 백준 4386번 - 별자리 만들기 ] 해설 및 코드

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

목적

선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오

 

접근법

1. MST를 구하는 문제이며, 크루스칼 알고리즘을 적용하자.

2. 실수연산을 최소화하기 위해서 별도 작업을 할 필요가 없는(하기도 애매한) 문제이다. 편하게 실수 연산을 하자.

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
const int N=100;
 
struct edge{
    int a,b;
    double c;
    bool operator<(const edge& oth)const{
        return c<oth.c;
    }
}ed[N*N];
double pos[N][2];
int p[N];
 
int find(int x){
    return p[x]<0?x:p[x]=find(p[x]);
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;cin>>n;
    memset(p,-1,4*n);
    f(i,0,n)cin>>pos[i][0]>>pos[i][1];
    int m=0;
    f(i,0,n)f(j,i+1,n){
        ed[m].a=i;
        ed[m].b=j;
        ed[m++].c=sqrt(pow(pos[i][0]-pos[j][0],2)+pow(pos[i][1]-pos[j][1],2));
    }
    sort(ed,ed+m);
    
    double ans=0;
    f(i,0,m){
        int ra=find(ed[i].a),rb=find(ed[i].b);
        if(ra==rb)continue;
        p[ra]=rb;
        ans+=ed[i].c;
    }
    cout<<fixed;
    cout.precision(2);
    cout<<ans;
    return 0;
}
 

 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.