BOJ 5081 - Constellations 링크
(2024.03.10 기준 G5)

문제

정수의 2차원 좌표로 표현이 되는 $n$개의 별이 있다. 각 별은 가장 가까운 별들과 하나의 별자리를 이루게 된다. 이때, 별자리의 개수 출력

알고리즘

각 별마다 유클리드 거리가 가장 가까운 별들을 찾아 하나의 별자리를 이루게 한다. 이를 모든 별마다 적용

풀이

지문을 읽어보면 모든 별은 가장 가까운 별들과 연결되며, 연결 요소 즉 집합의 개수를 구하라는 말이다. 일단 분리 집합 문제임은 자명하다. 거리는 문제에서 명시가 되어 있지 않지만 유클리드 거리를 구해 확인하면 된다. 단 부동 소수점 오차를 피하기 위해 제곱 형태를 사용하자.

모든 별마다 가장 가까운 별들을 구해 union하면 되는데, 이는 $n$이 최대 $500$ 밖에 되지 않아서 브루트포싱이 가능해진다. $n$이 더 커지면 $O(n \log n)$에 수행하는 보로노이를 사용해야 할건데, 이 알고리즘은 매우 어렵다. 시간이 날 때 한번 찾아보는 것을 추천한다.

코드

• C++

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> pii;

const int MAXN = 500, inf = INT_MAX;

int pa[MAXN];
pii p[MAXN];

// 두 점의 거리
int dist(pii a, pii b){
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

// 부모 노드 반환
int find(int u){
    if (pa[u] != u) pa[u] = find(pa[u]);
    return pa[u];
}

// 두 노드를 합치기
void merge(int u, int v){
    u = find(u); v = find(v);
    if (u < v) pa[v] = u;
    else pa[u] = v;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    for (int s = 1; n; ++s, cin >> n){
        for (int i = 0; i < n; i++) cin >> p[i].x >> p[i].y;

        // 가장 거리가 가까운 별들을 찾아 하나의 별자리(집합)으로 합친다.
        iota(pa, pa + n, 0);
        vector<int> res1;
        for (int i = 0; i < n; i++){
            int D = inf;
            for (int j = 0; j < n; j++){
                if (i == j) continue;
                int d = dist(p[i], p[j]);
                if (D == d) res1.push_back(j);
                else if (D > d){
                    D = d;
                    res1.clear();
                    res1.push_back(j);
                }
            }
            for (auto j: res1) merge(i, j);
        }

        // 각 별이 속해 있는 별자리의 개수를 센다.
        set<int> res2;
        for (int i = 0; i < n; i++) res2.insert(find(i));

        cout << "Sky " << s << " contains " << res2.size() << " constellations.\n";
    }
}

• Python

import sys; input = sys.stdin.readline
from math import inf

# 두 점의 거리
def dist(a, b):
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2

# 부모 노드 반환
def find(u):
    if pa[u] != u:
        pa[u] = find(pa[u])
    return pa[u]

# 두 노드를 합치기
def union(u, v):
    u = find(u); v = find(v)
    if u < v:
        pa[v] = u
    else:
        pa[u] = v

s = 1
while True:
    n = int(input())
    if not n:
        break

    p = [tuple(map(int, input().split())) for _ in range(n)]

    # 가장 거리가 가까운 별들을 찾아 하나의 별자리(집합)으로 합친다.
    pa = [i for i in range(n)]
    res1 = []
    for i in range(n):
        D = inf
        for j in range(n):
            if i == j:
                continue
            d = dist(p[i], p[j])
            if D == d:
                res1.append(j)
            elif D > d:
                D = d
                res1.clear()
                res1.append(j)
        for j in res1:
            union(i, j)

    # 각 별이 속해 있는 별자리의 개수를 센다.
    res2 = set()
    for i in range(n):
        res2.add(find(i))

    print('Sky %d contains %d constellations.' % (s, len(res2)))
    s += 1