ARCTIC (중하, p.450)

문제#

image.png


어떻게 풀었나?#

Union-Find(Disjoint Set)과 Binary Search를 이용해 풀었다.


정답 코드#

#include <bits/stdc++.h>
using namespace std;
int n;
double x[101], y[101];
int p[101];
int cnt[101];
inline void Init(int n) {
    for(int i=0; i<n; i++) {
        p[i] = i;
        cnt[i] = 1;
    }
}
int Find(int x) {
    if(x==p[x]) return p[x];
    else return p[x] = Find(p[x]);
}
bool Uni(int x, int y) {
    x = Find(x);
    y = Find(y);
    if(x==y) return false;
    if(x>y) swap(x,y);
    p[y] = x;
    cnt[x] += cnt[y];
    return true;
}
inline double Diff(double x, double y) {
    double ret = x-y;
    if(ret<0) return -ret;
    else return ret;
}
double Dist(int i, int j) {
    double dx = x[i]-x[j];
    double dy = y[i]-y[j];
    return sqrt(dx*dx + dy*dy);
}
bool Judge(double d) {
    Init(n);
    for(int i=0; i<n; i++) {
        for(int j=i+1; j<n; j++) {
            if(Dist(i,j) < d + 1e-12) {
                if (Uni(i, j)) {
                    if (cnt[Find(i)] == n) return true;
                }
            }
        }
    }
    return false;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        cin >> n;
        for(int i=0; i<n; i++) {
            cin >> x[i] >> y[i];
        }

        double lo=0, hi=2000;
        while (Diff(lo,hi)>1e-12) {
            double mid = (lo+hi)/2;
            if(Judge(mid)) hi=mid;
            else lo=mid;
        }
        printf("%.2lf\n", hi);
    }
    return 0;
}

Comment#

난이도 ‘하’는 정말 PS공부를 한번도 해본 적 없는 사람들 조차 맞출 수 있는 문제라 생각해서 ‘중하’정도로 올렸다. 아직 책 풀이법을 보지 않았는데, Disjoint-Set(Union-Find)을 모른다면 모든 점을 다 이을 수 있는지 확인하는 게 여러모로 귀찮을 것 같았다.

또, double 변수에 대한 이분탐색으로 정수형 변수에 대한 이분탐색과는 좀 다르다. 그렇다고 문제가 어려운건 아니지만, 정말 이런 문제를 처음 접해본 사람이라면 헤맬 수도 있지 않을까 생각했다.

확실히 종만북은 정말 갓책인 것 같다. 보통 하나의 문제에도 최소 3개의 기본적인 PS관련 트릭을 알고 있는지 묻고 있는데, 문제 하나하나가 다 주옥같다는 생각이 든다.


책 풀이법을 보니 그냥 BFS로 Judge()부분을 해결했는데, 크루스칼 최소 스패닝 트리를 언급하는 걸 보니 Union-Find 풀이법도 있다는 걸 말하고 있긴 하다.