[C/C++] 백준 #2261 가장 가까운 두 점(분할 정복)

#2261 문제는 분할 정복의 대표격인, 병합정렬, 퀵정렬, 히스토그램과 함께 자주 나옵니다.

 

문제의 링크입니다.

https://www.acmicpc.net/problem/2261

2261번: 가장 가까운 두 점

분할 정복과 관련한 게시글은 다음과 같습니다.

https://sdev.tistory.com/904

[C/C++] 백준 #1780 종이의 개수(분할정복)

https://sdev.tistory.com/852

[C/C++] 백준 #1725 히스토그램(분할 정복)

분할 정복은 분할 과정과 정복 과정이 있습니다.  분할 과정은 이해하기 좋지만, 정복 과정은 이해하기 어려울 수 있습니다.

 

가장 가까운 두 점에서의 핵심은 분할하여 얻은 결과를 가지고, 중심부에 있는 가장 가까운 점들을 찾는 부분을 줄이는 것입니다.

 

divide and conquer

그림에서와 같이 파란선을 기준으로 분할을 합니다.  동등한 개수의 점이 존재하도록 균등분할을 하면 됩니다.  왼쪽에 있는 점들로 가장 가까운 두 점의 거리를 구합니다.  마찬가지로 오른쪽에 있는 점들로 가장 가까운 두 점의 거리를 구합니다.  그러면, 왼쪽과 오른쪽 중 더 가까운 거리를 일단 해답으로 설정합니다.  이러면 왼쪽과 오른쪽에 있는 점들 사이, 즉, 파란선을 지나치는 두 점의 거리중 가까운 점을 찾으면, 우리는 이미 찾은 가까운 거리보다 이게 더 가까우면 이것을 선택하고, 그렇지 않으면 이미 찾은 값을 선택하면 됩니다.

 

모든 경우를 찾기보다, 파란색 선을 기준으로 이미 찾은 가장 가까운 두점의 거리를 경계로 노란색 경계를 설정합니다.  이로써, 우리는 거리 계산해야 하는 점들의 개수를 줄일 수 있습니다.  세로축에 대해서 정렬을 합니다.  그런후에 거리를 계산하면 됩니다.  이때 정렬하는 알고리즘 자체가 \(O(N \log N)\)이지만, 개수가 많이 줄어있기도 하고, 최악의 경우를 따져도 큰 문제가 없습니다.

 

시간복잡도 계산은 조금 복잡합니다.  최악의 경우를 가정한다면, 다음과 같이 따질 수가 있습니다.

\[ T(N) = 2T(N/2) + O(N) + O(N \log N) \]

 

사실 \(O(N)\) 항목이 애매한 부분이긴 하지만, 평균적인 경우로 따져보았을 때입니다.

마스터 정리에 의하면, \( T(N) = O(N \log N) \) 이라고 할 수 있습니다.

 

이제 와서 소스를 살펴보니 잘못 짠 부분이 있습니다.  노란색 영역의 왼쪽 부분과 오른쪽 부분과 구별해서 비교했어야 하는 지점, 이미 가로축으로 정렬되어 있으니, 이분탐색을 통해서 빠르게 노란색 영역을 구했으면 하는 점들이 아쉽네요.

 

제가 작성한 소스입니다.

//--------------------------------------
//    baekjoon #2261 - Nearest two points
//        - by Aubrey Choi
//        - created at 2021-07-24
//--------------------------------------
#include <stdio.h>
#include <algorithm>
int MIN(int a, int b) { return (a<b)?a:b; }
struct Point { int x, y; };
int *idx;
int sqr(int x) { return x*x; }
int getMin(Point v[], int a, int b)
{
    if(a == b) return 1000000000;
    if(a+1 == b) return sqr(v[a].x-v[b].x)+sqr(v[a].y-v[b].y);
    int c = (a+b)/2;
    int rmin = getMin(v, a, c);
    rmin = MIN(rmin, getMin(v, c+1, b));
    int k = 0;
    for(int i = c; i >= a; i--)
    {
        if(sqr(v[i].x-v[c+1].x) >= rmin) break;
        idx[k++] = i;
    }
    for(int i = c+1; i <= b; i++)
    {
        if(sqr(v[i].x-v[c].x) >= rmin) break;
        idx[k++] = i;
    }
    std::sort(idx, idx+k, [v](int a, int b) { return v[a].y < v[b].y; });
    for(int i = 0; i < k-1; i++)
    {
        int cx = v[idx[i]].x, cy = v[idx[i]].y;
        for(int j = i+1; j < k; j++)
        {
            int d = sqr(v[idx[j]].y-cy);
            if(d >= rmin) break;
            d += sqr(v[idx[j]].x-cx);
            if(d < rmin) rmin = d;
        }
    }
    return rmin;
}

int main()
{
    int n;
    scanf("%d", &n);
    Point *v = new Point[n];
    idx = new int[n];
    for(int i = 0; i < n; i++) scanf("%d%d", &v[i].x, &v[i].y);
    std::sort(v, v+n, [](Point a, Point b) { return a.x<b.x; });
    printf("%d\n", getMin(v, 0, n-1));
}