가장 가까운 점 쌍 ① — 분할 정복과 O(n log²n)

2차원 평면에 $n$개의 점이 흩어져 있다. 이 중 가장 가까운 두 점을 찾아라. 계산 기하(computational geometry)의 대표적인 문제로, 그림으로 보면 직관적이지만 막상 코드로 풀면 주의할 점이 많다.

---

문제와 브루트포스

입력은 2차원 좌표 $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$이다. 두 점 $p_i$, $p_j$ 사이의 유클리드 거리는

$$d(p_i, p_j) = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$$

이고, 이 값을 최소화하는 쌍을 찾으면 된다.

가장 단순한 풀이는 모든 쌍을 비교하는 것이다. $\binom{n}{2} = \frac{n(n-1)}{2}$ 쌍이 있으므로 $O(n^2)$이다.

이보다 빠를 수 없을까? 놀랍게도 목표는 $O(n \log n)$ 이다. 그리고 이 목표가 합리적이라는 단서는 정렬에 있다. 가장 가까운 두 원소를 찾는 문제는 — 자세한 이유는 아래에서 살펴보겠지만 — 정렬과 동등한 수준의 어려움을 가진다. 정렬의 하한이 $\Omega(n \log n)$이니, 목표도 $O(n \log n)$이 된다.

이 글에서 유도하는 알고리즘은 $O(n \log^2 n)$이고, 2편에서 이를 $O(n \log n)$으로 개선한다.

---

1차원에서 먼저

본격적으로 2차원으로 가기 전에, 1차원에서 같은 문제를 생각해 보자. 수직선 위에 $n$개의 수가 있을 때, 가장 가까운 두 수의 쌍을 찾아라.

직관적으로 바로 보인다. 정렬하면 끝이다. 정렬하면 가장 가까운 쌍은 반드시 인접한 쌍 안에 있고, 인접한 $n-1$쌍을 한 번만 훑으면 된다. 전체 복잡도는 정렬 $O(n \log n)$.

그런데 왜 정렬을 해야만 하는가? 정렬 없이 가장 가까운 쌍을 찾을 수 있다면 $O(n \log n)$보다 빠를 수도 있지 않을까?

그렇지 않다. 1차원 가장 가까운 쌍을 풀면 element uniqueness, 즉 “주어진 $n$개 값이 모두 서로 다른가”를 곧바로 답할 수 있다. 가장 가까운 두 값의 거리가 0인지 보면 되기 때문이다. 그리고 element uniqueness는 대수적 결정 트리(algebraic decision tree) 모형에서 $\Omega(n \log n)$이 하한임이 알려져 있다. 1차원 가장 가까운 쌍은 그 문제를 풀어 주므로 같은 모형에서 같은 하한을 갖는다. 정렬 후 인접 쌍 비교가 이 하한에 닿으니 최적이다.

2차원에서는 한 좌표만으로 거리를 판단할 수 없으니, 정렬만으로는 충분하지 않다. 여기서 분할 정복이 등장한다.

---

2차원 분할 정복

분할 정복의 세 단계 — 나누기, 풀기, 합치기 — 를 가장 가까운 점 쌍 문제에 적용한다.

나누기. 점들을 x좌표 기준으로 정렬한 뒤, 중앙을 기준으로 왼쪽 절반과 오른쪽 절반으로 나눈다.

풀기. 왼쪽 절반에서 가장 가까운 거리 $D_L$을, 오른쪽 절반에서 $D_R$을 각각 재귀로 구한다. (귀납적으로 각 절반의 문제는 올바르게 풀린다고 가정한다.)

합치기. 두 영역의 최솟값을 합치면

$$D = \min(D_L, D_R)$$

그런데 이것만으로는 끝이 아니다. 분할선을 가로지르는 쌍, 즉 한 점은 왼쪽 영역에, 다른 점은 오른쪽 영역에 있는 쌍도 확인해야 한다. 그리고 이 Combine 단계가 알고리즘의 핵심이다.

---

Combine: 경계의 밴드

합치기 단계에서 분할선을 가로지르는 쌍 중 현재 최솟거리 $D$보다 짧을 가능성이 있는 쌍은 어디에 있는가? 답은 밴드 안이다.

분할선에서 x좌표 차이가 $D$를 넘는 쌍은 x좌표 차이만으로도 이미 거리가 $D$ 이상이라 $D$를 갱신할 수 없다. 따라서 밴드 안 점들만 반대편의 밴드 점과 비교하면 된다.

그런데 이걸로 충분할까? 밴드 안 점이 너무 많으면 어떻게 되는가? 최악의 경우, 모든 점이 밴드 안에 있을 수 있다. 그러면 밴드 안 점을 모두 비교하는 비용이 $O(n^2)$이 되어, 분할 정복을 쓴 의미가 없다.

이 문제를 해결하는 것이 다음 단계다.

---

한 점은 다음 7개만 비교하면 된다

그러므로 Combine 알고리즘은 다음과 같다.

1. 밴드 안에 있는 점들(x좌표 차이의 제곱이 $d$ 이하인 점들, 여기서 $d$는 현재 최솟거리의 제곱)을 추린다.
2. 이 점들을 y좌표로 정렬한다.
3. 각 점에서 y좌표 기준 위쪽 7개 점과의 거리를 계산해 $d$를 갱신한다.

---

복잡도 — $O(n \log^2 n)$

---

코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

// 두 점 사이 거리의 제곱 반환 (루트 회피, long long 사용)
ll dist2(pll a, pll b) {
    ll dx = a.first  - b.first;
    ll dy = a.second - b.second;
    return dx * dx + dy * dy;
}

// y좌표 오름차순 정렬용 비교 함수
bool compY(const pll& a, const pll& b) {
    return a.second < b.second;
}

// arr[st..ed] 는 x좌표로 정렬된 상태.
// 반환값: 이 구간에서 가장 가까운 두 점 거리의 제곱.
// 함수 종료 시 arr[st..ed] 는 x좌표로 재정렬됨.
ll divideAndConquer(vector<pll>& arr, int st, int ed) {
    // ── 기저 사례 ──────────────────────────────────────────────
    if (ed == st) return LLONG_MAX;           // 점 1개: 비교 불가
    if (ed - st == 1) return dist2(arr[st], arr[ed]); // 점 2개

    // 점 3개: 세 쌍 중 최솟값 직접 계산
    if (ed - st == 2) {
        ll d = min({ dist2(arr[st], arr[st+1]),
                     dist2(arr[st+1], arr[ed]),
                     dist2(arr[st], arr[ed]) });
        // x재정렬은 이미 정렬된 상태이므로 생략
        return d;
    }

    // ── 분할 + 재귀 ────────────────────────────────────────────
    int mid = (st + ed) / 2;
    ll le = divideAndConquer(arr, st, mid);   // 왼쪽 재귀
    ll ri = divideAndConquer(arr, mid + 1, ed); // 오른쪽 재귀
    ll d = min(le, ri);                       // 현재 최솟거리 제곱

    // ── Combine: 밴드 안 점 추리기 ────────────────────────────
    // x좌표 차이 제곱이 d 이하인 점만 밴드에 포함.
    // (실제 x거리 기준으론 √d = D이지만, 제곱으로 비교)
    ll midX = arr[mid].first;
    int le_idx = mid, ri_idx = mid + 1;

    while (le_idx > st &&
           (midX - arr[le_idx - 1].first) * (midX - arr[le_idx - 1].first) <= d)
        le_idx--;
    while (ri_idx < ed &&
           (arr[ri_idx + 1].first - midX) * (arr[ri_idx + 1].first - midX) <= d)
        ri_idx++;

    // ── 밴드 점을 y좌표로 정렬 ────────────────────────────────
    sort(arr.begin() + le_idx, arr.begin() + ri_idx + 1, compY);

    // ── 한 점에서 위쪽 최대 7개 비교 ─────────────────────────
    for (int i = le_idx; i <= ri_idx; i++) {
        for (int j = 1; j <= 7; j++) {
            if (i + j > ri_idx) break;
            ll td = dist2(arr[i], arr[i + j]);
            d = min(d, td);
        }
    }

    // ── x좌표로 재정렬 (상위 호출의 Combine을 위해) ───────────
    sort(arr.begin() + st, arr.begin() + ed + 1);

    return d;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<pll> arr(n);
    for (auto& [x, y] : arr) cin >> x >> y;

    // 초기 x좌표 정렬
    sort(arr.begin(), arr.end());

    ll ans = divideAndConquer(arr, 0, n - 1);
    // ans는 최솟거리의 제곱. 실제 거리가 필요하면 sqrt(ans).
    cout << ans << "\n";

    return 0;
}

코드 흐름 요약:

단계	설명	비용
초기 sort	x좌표 정렬	$O(n \log n)$
기저 사례	크기 1·2·3에서 직접 계산	$O(1)$
재귀	좌우 절반씩 분리해 반환값 = 거리 제곱	—
밴드 추리기	x차이 제곱 $\le d$ 인 점만 선택	$O(n)$
y정렬	밴드 점을 y좌표로 정렬	$O(n \log n)$
7개 비교	각 점에서 위 최대 7개 검사	$O(n)$
x재정렬	상위 레벨 Combine 준비	$O(n \log n)$

---