백준[1774] 우주신과의 교감

문제설명

풀이 방법

크루스칼 알고리즘을 이용하여 풀이한다. 이미 연결 된 간선은 미리 연결해놓고 가장 거리가 짧은 간선을 뽑아 사이클이 있는지 확인하고 연결한다. 

 

코드

우선순위큐를 이용한 구현

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <vector>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pdll = pair<double, pll>;

pll arr[1003];
ll N, M, par[1003], cnt, lev[1003];
priority_queue<pdll, vector<pdll>, greater<pdll>> pq;

ll dist(pll a, pll b) {
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

int find(int x) {
    if (par[x] == x) return x;
    return par[x] = find(par[x]);
}

bool merge(int x, int y) {
    int a = find(x), b = find(y);
    if (a == b) return false;
    if (lev[a] > lev[b]) swap(a, b);
    if (lev[a] == lev[b]) lev[a]++;
    par[a] = b;
    return true;
}

int main() {
    scanf("%lld %lld", &N, &M);
    for (int i = 1; i <= N; i++) {
        scanf("%lld %lld", &arr[i].first, &arr[i].second);
        par[i] = i;
        lev[i] = 1;
    }
    for (int i = 1; i <= N; i++) 
        for (int j = i + 1; j <= N; j++) 
            pq.push({dist(arr[i], arr[j]), {i, j}});

    for (int i = 0; i < M; i++) {
        ll a, b; scanf("%lld %lld", &a, &b);
        if (merge(a, b)) cnt++;
    }

    double ans = 0;
    while (!pq.empty() && cnt != N - 1) {
        double d = pq.top().first;
        auto [x, y] = pq.top().second;
        pq.pop();
        if (merge(x, y)) {
            ans += sqrt(d); cnt++;
        }
    }
    printf("%.2lf", ans);
}

배열의 정렬을 이용한 구현

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <vector>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pdll = pair<double, pll>;

pll arr[1003];
ll N, M, par[1003], cnt;

ll dist(pll a, pll b) {
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

int find(int x) {
    if (par[x] == x) return x;
    return par[x] = find(par[x]);
}

bool merge(int x, int y) {
    int a = find(x), b = find(y);
    if (a == b) return false;
    par[a] = b;
    return true;
}

int main() {
    scanf("%lld %lld", &N, &M);
    for (int i = 1; i <= N; i++) {
        scanf("%lld %lld", &arr[i].first, &arr[i].second);
        par[i] = i;
    }
    vector<pdll> v;
    for (int i = 1; i <= N; i++) 
        for (int j = i + 1; j <= N; j++) 
            v.push_back({dist(arr[i], arr[j]), {i, j}});
    sort(v.begin(), v.end());

    for (int i = 0; i < M; i++) {
        ll a, b; scanf("%lld %lld", &a, &b);
        if (merge(a, b)) cnt++;
    }

    double ans = 0;
    for (int i = 0; i < v.size(); i++) {
        if (cnt == N - 1) break;
        auto [x, y] = v[i].second;
        if (merge(x, y)) {
            cnt++;
            ans += sqrt(v[i].first);
        }
    }
    printf("%.2lf", ans);
}

거리를 구할때 오버플로우가 발생 할 수 있다. 조심하자

 

문제링크: https://www.acmicpc.net/problem/1774