[BOJ] 1774. 우주신과의 교감 (C++)

문제

2차원 좌표에서 이미 연결된 통로가 존재한다. 모든 우주선끼리 연결해야하는데, 추가로 연결해야 할 통로의 길이 합이 최소가 되도록 통로 연결하기

생각할 것

• 중복된 데이터가 들어갈 수 있음

반례

4 2
1 1
3 1
2 3
4 3
1 4
4 1 
정답 : 4.00

union연산을 할 때만 count를 올리도록 코드를 변경했더니 정답이었다

코드

#include <iostream>
#include <vector>
#include <utility>
#include <cmath>
#include <queue>

using namespace std;

struct Edge {
    int start, end;
    double cost;
};

struct cmp {
    bool operator()(Edge &e1, Edge &e2) {
        return e1.cost > e2.cost;
    }
};

int find(int a, vector<int> &parent) {
    if (parent[a] == a) return a;
    return parent[a] = find(parent[a], parent);
}

void merge(int a, int b, int &count, vector<int> &parent) {
    int pa = find(a, parent);
    int pb = find(b, parent);
    if (pa != pb) {
        parent[pb] = pa;
        count++;
    }
}

int main() {
    int N, M, X, Y;
    cin >> N >> M;

    // 우주신 좌표
    vector<pair<int, int>> god(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> X >> Y;
        god[i] = {X, Y};
    }

    // 이미 연결된 통로 합치기
    vector<int> parent(N + 1);
    int count = 0;
    for (int i = 0; i <= N; i++) parent[i] = i;
    for (int i = 0; i < M; i++) {
        cin >> X >> Y;
        merge(X, Y, count, parent);
    }

    // 연결되지 않은 통로에서 가능한 길을 모두 넣기
    priority_queue<Edge, vector<Edge>, cmp> pq;
    for (int i = 1; i < N; i++) {
        for (int j = i + 1; j <= N; j++) {
            double cost = sqrt(pow(god[i].first - god[j].first, 2) + pow(god[i].second - god[j].second, 2));
            pq.push({i, j, cost});
        }
    }

    // 크루스칼
    double res = 0;
    while (count < N - 1) {
        Edge edge = pq.top();
        pq.pop();
        if (find(edge.start, parent) == find(edge.end, parent)) continue;
        merge(edge.start, edge.end, count, parent);
        res += edge.cost;
    }

    printf("%.2f", res);

    return 0;
}