가장 가까운 점 쌍 문제(Closest Pair of Points) – 분할 정복으로 O(n log n)에 풀기

문제 개요

이 문제에서는 2차원 평면 위에 n개의 점이 주어집니다. 우리가 구해야 할 것은 이 점들 중 서로 간의 거리가 가장 짧은 점 쌍(pair)입니다.

이 문제를 효율적으로 해결하려면 먼저 점들을 두 개의 절반으로 나눈 뒤, 각 영역 안에서 최소 거리를 재귀적으로 계산합니다. 이어서 중앙선을 기준으로 일정 거리 이내에 있는 점들을 스트립(strip) 형태로 모아, 스트립 배열 안에서도 최소 거리를 다시 확인합니다. 알고리즘 시작 시 두 개의 리스트를 준비하는데, 하나는 x좌표 기준으로 정렬된 점 목록이고, 다른 하나는 y좌표 기준으로 정렬된 점 목록입니다.

이 알고리즘의 시간 복잡도는 O(n log n)입니다. 단순히 모든 점 쌍을 비교하는 브루트 포스 방식(O(n²))보다 훨씬 빠릅니다.

입력과 출력

입력:
서로 다른 점들의 집합이 주어집니다.
(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)

출력:
주어진 점들 중 각 점 쌍 사이의 최소 거리를 구합니다.
여기서 최소 거리는 1.41421 단위입니다.

알고리즘

1. findMinDist(pointsList, n)

입력: 점 목록과 점의 개수
출력: 두 점 사이의 최소 거리

Begin
    min := ∞
    for all items i in the pointsList, do
        for j := i+1 to n-1, do
            if distance between pointList[i] and pointList[j] < min, then
                min = distance of pointList[i] and pointList[j]
        done
    done
    return min
End

2. stripClose(strips, size, dist)

입력: 스트립에 포함된 점들, 점의 개수, 중앙선으로부터의 거리(dist)
출력: 스트립 내 두 점 사이의 최근접 거리

Begin
    for all items i in the strip, do
        for j := i+1 to size-1 and (y difference of ith and jth points) < min, do
            if distance between strip[i] and strip[j] < min, then
                min = distance of strip[i] and strip[j]
        done
    done
    return min
End

3. findClosest(xSorted, ySorted, n)

입력: x좌표 기준 정렬된 점 목록, y좌표 기준 정렬된 점 목록, 점의 개수
출력: 전체 점 집합에서의 최소 거리

Begin
    if n <= 3, then
        call findMinDist(xSorted, n)
        return the result
    mid := n/2
    midPoint := xSorted[mid]
    define two sub lists of points to separate points along vertical line.
    the sub lists are, ySortedLeft and ySortedRight

    leftDist := findClosest(xSorted, ySortedLeft, mid)           // 왼쪽 영역의 최소 거리
    rightDist := findClosest(xSorted + mid, ySortedRight, n-mid) // 오른쪽 영역의 최소 거리

    dist := minimum of leftDist and rightDist

    make strip of points
    j := 0
    for i := 0 to n-1, do
        if |difference of ySorted[i].x and midPoint.x| < dist, then
            strip[j] := ySorted[i]
            j := j+1
    done

    close := stripClose(strip, j, dist)
    return minimum of close and dist
End

C++ 구현 예시

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

struct point {
    int x, y;
};

int cmpX(point p1, point p2) {      // x값 기준 정렬용 비교 함수
    return (p1.x < p2.x);
}

int cmpY(point p1, point p2) {      // y값 기준 정렬용 비교 함수
    return (p1.y < p2.y);
}

float dist(point p1, point p2) {    // p1과 p2 사이의 거리 계산
    return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}

float findMinDist(point pts[], int n) {   // 집합 내 두 점 사이의 최소 거리(브루트 포스)
    float min = 9999;
    for (int i = 0; i < n; ++i)
        for (int j = i+1; j < n; ++j)
            if (dist(pts[i], pts[j]) < min)
                min = dist(pts[i], pts[j]);
    return min;
}

float min(float a, float b) {
    return (a < b)? a : b;
}

float stripClose(point strip[], int size, float d) {   // 스트립 내 두 점의 최근접 거리
    float min = d;
    for (int i = 0; i < size; ++i)
        for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j)
            if (dist(strip[i], strip[j]) < min)
                min = dist(strip[i], strip[j]);
    return min;
}

float findClosest(point xSorted[], point ySorted[], int n){
    if (n <= 3)
        return findMinDist(xSorted, n);
    int mid = n/2;

    point midPoint = xSorted[mid];
    point ySortedLeft[mid+1];       // 왼쪽 영역의 y 정렬 점들
    point ySortedRight[n-mid-1];    // 오른쪽 영역의 y 정렬 점들
    int leftIndex = 0, rightIndex = 0;

    for (int i = 0; i < n; i++) {   // y 정렬 점들을 왼쪽/오른쪽으로 분리
        if (ySorted[i].x <= midPoint.x)
            ySortedLeft[leftIndex++] = ySorted[i];
        else
            ySortedRight[rightIndex++] = ySorted[i];
    }

    float leftDist = findClosest(xSorted, ySortedLeft, mid);
    float rightDist = findClosest(xSorted + mid, ySortedRight, n-mid);
    float dist = min(leftDist, rightDist);

    point strip[n];                 // 수직선에 가까운 점들을 저장
    int j = 0;

    for (int i = 0; i < n; i++)
        if (abs(ySorted[i].x - midPoint.x) < dist) {
            strip[j] = ySorted[i];
            j++;
        }
    return min(dist, stripClose(strip, j, dist));   // dist와 스트립 내 최근접 쌍으로 최종 최솟값 계산
}

float closestPair(point pts[], int n) {   // 점 집합에서 최근접 점 쌍의 거리 계산
    point xSorted[n];
    point ySorted[n];

    for (int i = 0; i < n; i++) {
        xSorted[i] = pts[i];
        ySorted[i] = pts[i];
    }

    sort(xSorted, xSorted+n, cmpX);
    sort(ySorted, ySorted+n, cmpY);
    return findClosest(xSorted, ySorted, n);
}

int main() {
    point P[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
    int n = 6;
    cout << "The minimum distance is " << closestPair(P, n);
}

실행 결과

The minimum distance is 1.41421

핵심 포인트

이 알고리즘이 빠른 이유는 스트립 검사 단계에 있습니다. 중앙선 근처의 스트립 안에서는 각 점이 자신보다 y좌표가 큰 점들과만 비교되며, 이미 계산된 최소 거리(dist)보다 y 차이가 큰 점은 즉시 건너뜁니다. 기하학적 성질에 의해 한 점과 비교해야 하는 점은 최대 7개(상수 개수)로 제한되므로, 스트립 검사는 선형 시간에 처리됩니다. 덕분에 전체 알고리즘의 복잡도가 정렬 비용인 O(n log n)으로 유지됩니다.