문제

문제 링크

문제 접근

  • 이 문제는 모든 노드가 연결되는 최소 엣지를 찾는 MST를 구하는 문제이다.
  • 여기서 문제는 가장 짧은 거리를 구해야한다는 것이다.
  • 이를 위해서 priority queue를 이용해서 미리 거리를 다 구해놓고 하나씩 연결해가면서 싸이클이 발생하는지 확인하는 과정을 진행하였다.

코드

#include <cstdio>
#include <queue>
#include <cmath>
#define pii pair<int, int>
#define pdp pair<double, pii>
using namespace std;

int n, m, v1, v2, par[1002], X[1002], Y[1002];

double sqr(double d){return d*d;}

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

int Union(int x, int y){
    int px = find(x), py = find(y);
    if(px == py)return 0;
    par[px] = py;
    return 1;
}

int main(){
    double ans = 0;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d %d", &X[i], &Y[i]);
        par[i] = i;
    }
    for(int i = 0; i < m; i++){
        scanf("%d %d", &v1, &v2);
        Union(v1, v2);
    }
    priority_queue<pdp> pq;
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            double d = sqr(X[i] - X[j]) + sqr(Y[i] - Y[j]);
            pq.push(pdp(-d, pii(i, j)));
        }
    }
    int cnt = m;
    while(!pq.empty() && cnt != n - 1){
        pdp top = pq.top(); pq.pop();
        double tv = top.first;
        int tx = top.second.first, ty = top.second.second;
        if(Union(tx, ty))ans += sqrt(-tv), cnt++;
    }
    printf("%.2f", ans);
}

느낀점

  • 타입을 float으로 하니까 100000*100000의 값을 이상하게 담아내는 것을 확인할 수 있었다.
  • 필요한 변수형이 뭔지 확인하고 문제를 풀도록 하자.