[코드트리] 최소 거리 잇기 C++

문제

https://www.codetree.ai/missions/9/problems/minimum-distance?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드

float과 double의 정밀도 차이

 

• float은 32비트(4바이트) 자료형, 약 7자리 정도의 십진수 정밀도
• double은 64비트(8바이트) 자료형, 약 15~16자리 정도의 십진수 정밀도

문제에서 점의 좌표는 최대 1,000,000까지 주어진다.

두 점 사이의 거리 공식 sqrt((x2 - x1)^2 + (y2 - y1)^2)을 계산하면, 그 결과 값 역시 매우 큰 값이 될 수 있다.

float의 정밀도로는 필요한 정확도를 보장하기 어려움.

 

#include <iostream>
#include <iomanip> //setprecision
#include <vector>
#include <tuple>
#include <cmath> // pow, sqrt
#include <algorithm> // sort

using namespace std;

const int MAX_N = 200;
const int MAX_M = 200;

int n, m;
int uf[MAX_N+1]; // i번째 점의 소속
vector<pair<int,int> > points; // {x, y}
vector<tuple<double,int,int> > edges; // {dist, a, b} a번 노드와 b번 노드의 거리 dist

int myFind(int x){
    if(uf[x]==x) return x;
    return uf[x]=myFind(uf[x]);
}
void myUnion(int x, int y){
    x=myFind(x), y=myFind(y);
    if(x==y) return;
    uf[x]=y;
}

double distBetweenTwoPoints(pair<int,int> a, pair<int,int> b){
    // 두 점 사이의 거리: sqrt((x_2 - x_1)^2 + (y_2 - y_1)^2)
    return sqrt(pow(b.first-a.first, 2) + pow(b.second-a.second, 2));
}

int main() {
    cin >> n >> m;
    // uf 배열 초기화
    for(int i=1; i<=n; ++i){
        uf[i]=i;
    }
    // n개 줄에 걸쳐 각 점의 좌표
    points.resize(n+1);
    for(int i=1; i<=n; ++i){
        int x, y;
        cin >> x >> y;
        points[i]={x, y};
    }
    // m개 줄에 걸쳐 각 선이 잇고 있는 정점의 번호
    for(int i=1; i<=m; ++i){
        int a, b;
        cin >> a >> b;
        myUnion(a, b);
    }

    // 각 점들을 잇는 모든 간선 추가
    for(int i=1; i<=n; ++i){
        for(int j=i+1; j<=n; ++j){
            double dist = distBetweenTwoPoints(points[i], points[j]);
            edges.push_back({dist, i, j});
        }
    }

    // dist 순으로 정렬
    sort(edges.begin(), edges.end());
    
    double mstSum = 0.0;
    for(auto e : edges){
        double dist;
        int a, b;
        tie(dist, a, b)=e;
        if(myFind(a)==myFind(b)) continue;
        myUnion(a, b);
        mstSum+=dist;
    }

    // 소수점 둘째 자리까지 출력
    cout << fixed << setprecision(2) << mstSum << '\n';
    return 0;
}