C++로 배열에서 가장 가까운 점 쌍 찾기 (분할 정복 알고리즘)

평면상에 흩어진 여러 점 중에서 서로 가장 가까운 두 점, 즉 최근접 점 쌍(closest pair of points)을 찾는 문제는 계산 기하학의 고전적인 문제입니다. 모든 점 쌍을 일일이 비교하는 완전 탐색은 O(n²)의 시간이 걸리지만, 분할 정복(Divide and Conquer) 기법을 활용하면 O(n log n)으로 성능을 크게 개선할 수 있습니다. 아래는 그 원리를 구현한 C++ 프로그램입니다.

알고리즘

1. 스트립(strip) 영역에서 최근접 거리 계산

분할 경계 근처의 점들만 모아 놓은 스트립 배열을 y좌표 기준으로 정렬한 뒤, 인접한 점들끼리만 비교하여 현재까지의 최소 거리보다 더 가까운 쌍이 있는지 확인하는 함수입니다.

시작
   함수 Closest_dist_Spoint(poi stp[], int s, double dist, poi &pnt1, poi &pnt2)를 double형으로 선언한다.
   Minimum을 double형으로 선언하고 dist 값으로 초기화한다.
   for (int i = 0; i < s; ++i)
      for (int j = i+1; j < s && (stp[j].poi2 - stp[i].poi2) < Minimum; ++j)
         만약 Distance(stp[i], stp[j]) < Minimum이라면
            Minimum = Distance(stp[i], stp[j])
            pnt1.poi1 = stp[i].poi1, pnt1.poi2 = stp[i].poi2
            pnt2.poi1 = stp[j].poi1, pnt2.poi2 = stp[j].poi2
   Minimum을 반환한다.
끝.

2. 전체 최소 거리 계산

x좌표 기준으로 정렬된 점들을 중앙점을 기준으로 좌우로 나누어 각각 재귀적으로 최근접 거리를 구하고, 두 결과 중 작은 값을 기준으로 경계 스트립 영역까지 추가로 검사하여 최종 최소 거리를 구하는 핵심 함수입니다.

시작
   함수 Closest_dist(poi P[], poi stp[], int n, poi &pnt1, poi &pnt2)를 double형으로 선언한다.
   poi 구조체의 정적 객체 pt1, pt2, pt3, pt4를 선언한다.
   만약 n <= 3이라면 S_Distance(P, n, pt1, pt2)를 반환한다.
   medium을 정수형으로 선언하고 n/2로 초기화한다.
   mediumPoint를 poi 구조체 객체로 선언하고 P[medium]으로 초기화한다.
   D_Left를 double형으로 선언하고 Closest_dist(P, stp, medium, pt1, pt2)로 초기화한다. // 중앙점 왼쪽 영역
   D_Right를 double형으로 선언하고 Closest_dist(P + medium, stp, n - medium, pt3, pt4)로 초기화한다. // 중앙점 오른쪽 영역
   만약 D_Left < D_Right라면
      pnt1, pnt2에 왼쪽 부분의 점 쌍(pt1, pt2)을 저장한다.
   아니면
      pnt1, pnt2에 오른쪽 부분의 점 쌍(pt3, pt4)을 저장한다.
   min_dist를 double형으로 선언하고 Minimum(D_Left, D_Right)으로 초기화한다.
   j를 정수형으로 선언하고 0으로 초기화한다.
   for (int i = 0; i < n; i++)
      만약 abs(P[i].poi1 - mediumPoint.poi1) < min_dist라면
         stp[j++] = P[i]
   min_dist_strip을 double형으로 선언하고 Closest_dist_Spoint(stp, j, min_dist, pt1, pt2)로 초기화한다.
   F_Min을 double형으로 선언하고 min_dist로 초기화한다.
   만약 min_dist_strip < min_dist라면
      pnt1, pnt2에 새로 찾은 점 쌍을 저장하고 F_Min = min_dist_strip으로 설정한다.
   F_Min을 반환한다.
끝.

C++ 전체 예제 코드

#include <iostream>
#include <cfloat>
#include <cstdlib>
#include <cmath>
using namespace std;

struct poi {
   double poi1, poi2;
};

// x좌표 기준 오름차순 비교 함수
inline int Comp_poi1(const void* x, const void* b) {
   poi *p1 = (poi *)x, *pnt2 = (poi *)b;
   return (p1->poi1 - pnt2->poi1);
}

// y좌표 기준 오름차순 비교 함수
inline int Comp_poi2(const void* x, const void* y) {
   poi *pnt1 = (poi *)x, *pnt2 = (poi *)y;
   return (pnt1->poi2 - pnt2->poi2);
}

// 두 점 사이의 유클리드 거리 계산
inline double Distance(poi pnt1, poi pnt2) {
   return sqrt( (pnt1.poi1 - pnt2.poi1)*(pnt1.poi1 - pnt2.poi1) +
   (pnt1.poi2 - pnt2.poi2)*(pnt1.poi2 - pnt2.poi2) );
}

// 브루트 포스 방식으로 최소 거리 계산 (점이 3개 이하일 때 사용)
double S_Distance(poi P[], int n, poi &pnt1, poi &pnt2) {
   double min = DBL_MAX;
   for (int i = 0; i < n; ++i)
      for (int j = i+1; j < n; ++j)
         if (Distance(P[i], P[j]) < min) {
            min = Distance(P[i], P[j]);
            pnt1.poi1 = P[i].poi1, pnt1.poi2 = P[i].poi2;
            pnt2.poi1 = P[j].poi1, pnt2.poi2 = P[j].poi2;
         }
   return min;
}

// 두 값 중 작은 값 반환
inline double Minimum(double poi1, double poi2) {
   return (poi1 < poi2)? poi1 : poi2;
}

// 스트립 영역에서 최근접 점 쌍의 거리 계산
double Closest_dist_Spoint(poi stp[], int s, double dist, poi &pnt1, poi &pnt2) {
   double Minimum = dist; // 최소 거리를 dist로 초기화
   qsort(stp, s, sizeof(poi), Comp_poi2);
   for (int i = 0; i < s; ++i)
      for (int j = i+1; j < s && (stp[j].poi2 - stp[i].poi2) < Minimum; ++j)
         if (Distance(stp[i],stp[j]) < Minimum) {
            Minimum = Distance(stp[i], stp[j]);
            pnt1.poi1 = stp[i].poi1, pnt1.poi2 = stp[i].poi2;
            pnt2.poi1 = stp[j].poi1, pnt2.poi2 = stp[j].poi2;
         }
         return Minimum;
}

// 분할 정복으로 최소 거리 계산
double Closest_dist(poi P[], poi stp[], int n, poi &pnt1, poi &pnt2) {
   static poi pt1, pt2, pt3, pt4;
   if (n <= 3)
      return S_Distance(P, n, pt1, pt2);
   int medium = n/2; // 중앙점 계산
   poi mediumPoint = P[medium];
   double D_Left = Closest_dist(P, stp, medium, pt1, pt2); // 중앙점 왼쪽 영역의 최소 거리
   double D_Right = Closest_dist(P + medium, stp, n-medium, pt3, pt4); // 중앙점 오른쪽 영역의 최소 거리
   if(D_Left < D_Right) { // 더 가까운 점 쌍 저장
      pnt1.poi1 = pt1.poi1; pnt1.poi2 = pt1.poi2;
      pnt2.poi1 = pt2.poi1; pnt2.poi2 = pt2.poi2;
   } else {
      pnt1.poi1 = pt3.poi1; pnt1.poi2 = pt3.poi2;
      pnt2.poi1 = pt4.poi1; pnt2.poi2 = pt4.poi2;
   }
   double min_dist = Minimum(D_Left, D_Right);
   int j = 0;
   for (int i = 0; i < n; i++)
      if (abs(P[i].poi1 - mediumPoint.poi1) < min_dist)
         stp[j++] = P[i];
         double min_dist_strip = Closest_dist_Spoint(stp, j, min_dist, pt1, pt2);
         double F_Min = min_dist;
         if(min_dist_strip < min_dist) {
            pnt1.poi1 = pt1.poi1; pnt1.poi2 = pt1.poi2;
            pnt2.poi1 = pt2.poi1; pnt2.poi2 = pt2.poi2;
            F_Min = min_dist_strip;
         }
         return F_Min;
}

int main() {
   poi P[] = {{4, 1}, {15, 20}, {30, 40}, {8, 4}, {13, 11}, {5, 6}};
   poi pnt1 = {DBL_MAX, DBL_MAX}, pnt2 = {DBL_MAX, DBL_MAX}; // 배열에서 가장 가까운 점 쌍
   int n = sizeof(P) / sizeof(P[0]);
   qsort(P, n, sizeof(poi), Comp_poi1);
   poi *stp = new poi[n];
   cout << "The closest distance of point in array is: " << Closest_dist(P, stp, n, pnt1, pnt2) << endl;
   cout << "The closest pair of point in array: (" << pnt1.poi1 << "," << pnt1.poi2 << ") and ("
   << pnt2.poi1 << "," << pnt2.poi2 << ")" << endl;
   delete[] stp;
   return 0;
}

실행 결과

The closest distance of point in array is: 3.60555
The closest pair of point in array: (13,11) and (15,20)

정리

이 프로그램은 점들을 x좌표 기준으로 먼저 정렬한 뒤(O(n log n)), 중앙점을 기준으로 문제를 절반씩 나누어 재귀적으로 해결합니다. 각 단계에서 경계 스트립 검사는 y좌표 정렬 덕분에 각 점당 상수 번의 비교만으로 처리되므로, 전체 시간 복잡도는 O(n log n)이 됩니다. 완전 탐색의 O(n²)보다 훨씬 효율적이므로, 점의 개수가 많은 대규모 데이터에서 특히 유용하게 활용할 수 있습니다.