인프런 커뮤니티 질문&답변

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

//Kruskal
#include <bits/stdc++.h>

using namespace std;
int unf[1001];
struct Hotel{
    int number;
    int x;
    int y;
    
    Hotel(int number, int x, int y){
        this->number = number;
        this->x = x;
        this->y = y;
    }
};

struct Road{
    int st;
    int et;
    double val;

    Road(int st, int et, double val){
        this->st = st;
        this->et =et;
        this->val =val;
    }

    bool operator<(const Road &ref)const{ //kruskal MST는 간선을 정렬함
        return val < ref.val;
    }
};

int Find(int v){
    if(v==unf[v]) return v;
    else return unf[v] = Find(unf[v]);
}

void Union(int a, int b){
    a = Find(a);
    b = Find(b);
    if(a!=b) unf[a] = b;
}

double DistanceCalculator(Hotel st, Hotel et){
    double res = ((et.x - st.x) * (et.x - st.x) + (et.y - st.y) * (et.y - st.y));
    return sqrt(res);
}

int main(int argc, const char * argv[]) {
    //ios_base::sync_with_stdio(false);
    
    int N,M;
    cin >> N >> M;
    vector<Hotel> node;
    vector<Road> edge;
    int x,y;
    
    for(int i = 1; i <= N; i++) unf[i] = i;
    
    for(int i = 0; i < N; i++){
        cin >> x >> y;
        node.push_back(Hotel(x,y));
    }
    for(int i=0; i<=N; i++){
        for(int j=i+1; j<=N; j++){
            if(i != j){
                edge.push_back(Road(node[i].number, node[j].number, DistanceCalculator(node[node[i].number-1],node[node[j].number-1])));
            }
        }
    }
    
    int st,et;
    for(int i = 0; i < M; i++){
        cin >> st >> et;
        Union(st, et); //연결함. 이미 연결했기 때문에 나중에 고려 안함.
    }
    sort(edge.begin(), edge.end());
    
    double res = 0;
    for (int i = 0; i < edge.size(); i++) {
        int fa = Find(edge[i].st);//해당 노드의 집합 번호
        int fb = Find(edge[i].et);
        if(fa != fb){ // 같지 않으면 Cycle이 돌지 않으므로
            res += edge[i].val; // 최소비용에 누적
            Union(edge[i].st,edge[i].et); //집합 연결시켜주기
        }
    }
    
    printf("%0.2f",res);
    
    return 0;
}