백준 문제풀이

BOJ 9373.cpp

#include <bits/stdc++.h>
using namespace std;
// MST + 약간 그리디...? Joonas' Note 블로그 솔루션 많이 참고.
// < x좌표, y좌표, 반지름 >
typedef tuple<double, double, double> tp;

int T, N;
double W;
tp arr[1111];
struct edge{
    double A;
    double B;
    double dist;
    edge(){
        A = 0;
        B = 0;
        dist = 0.0;
    }
    edge(double a, double b, double d) : A(a), B(b), dist(d){}
    // 거리 작은 순으로 정렬할 거임
    bool operator<(const edge& e){
        return dist < e.dist;
    }
};
// 센서 사이 간격
double Between(tp t1, tp t2){
    double Distance = sqrt(((get<0>(t1)-get<0>(t2))*(get<0>(t1)-get<0>(t2))) + ((get<1>(t1)-get<1>(t2))*(get<1>(t1)-get<1>(t2))));
    double R = get<2>(t1)+get<2>(t2);
    if(Distance>=R) return Distance-R;
    else return 0.0;
}
int R[1111];
int Find(int x){
    if(R[x]<0) return x;
    return R[x]=Find(R[x]);
}
void Merge(int x, int y){
    int xRoot = Find(x);
    int yRoot = Find(y);
    if(xRoot==yRoot) return;
    // 루트 합쳐주기
    R[yRoot] = xRoot;
}
int main(){ios_base::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);

cin >> T;
while(T--){
    cin >> W;
    cin >> N;
    for (int i = 0; i < N; ++i){
        double a, b, c;
        cin >> a >> b >> c;
        arr[i] = tp(a,b,c);
    }
    vector<edge> V; // 각 센서들 및 왼쪽, 오른쪽 벽 사이 간격들을 저장할 벡터
    double Left = 0.0; // 왼쪽벽 -> index : N 로 생각
    double Right = (double)W; // 오른쪽 벽 -> index : N+1 로 생각
    V.push_back(edge(N,N+1,(double)W));
    for (int i = 0; i < N; ++i){
        // 각 센서와 왼쪽 벽 사이 간격 = x좌표 - 반지름
        double fromleft = get<0>(arr[i])-get<2>(arr[i]);
        if(fromleft<0.0) fromleft = 0.0;
        V.push_back(edge(i,N,fromleft)); // 왼쪽벽의 index 는 N
        // 각 센서와 오른쪽 벽 사이 간격 = 오른쪽벽 - (x좌표+반지름)
        double fromright = W-(get<0>(arr[i])+get<2>(arr[i]));
        if(fromright<0.0) fromright = 0.0;
        // 각각 벡터에 넣어
        V.push_back(edge(i,N+1,fromright)); // 오른쪽 벽의 index 는 N+1
        // 센서들 간의 간격
        for (int j = i+1; j < N; ++j)
            V.push_back(edge(i,j,Between(arr[i],arr[j])));
    }
    // 각 루트들 초기화
    memset(R,-1,sizeof(R));
    // 간격 작은 순으로 정렬
    sort(V.begin(),V.end());
    for(auto it: V){
        int x = it.A;
        int y = it.B;
        double path = it.dist;
        Merge(x,y);
// 작은 간격부터 보는 것이므로 왼쪽벽과 오른쪽 벽이 하나의 component로 합쳐졌다면 이때의 간격이 두 벽 사이의 최소 간격이다.
// 이후 간격들은 지금의 간격보다 크거나 같다.
        // 왼쪽벽과 오른쪽 벽이 합쳐졌다면
        if(Find(N)==Find(N+1)){
            cout<<fixed;
            cout.precision(6);
            cout << path/2.0 << '\n';
            break;
        }
    }
}
return 0;
}