[알고리즘] 9. Closest Pair

1. Closest Pair Idea

주어진 점들 중에서 가장 가까운 쌍을 찾는 문제 유형이다. 1차원인 경우에는 단순히 정렬을 통해서 구할 수 있고, 2차원의 경우 두 점 사이의 거리 공식을 이용해 일일이 비교하여 구할 수 있다. 하지만 이 경우 시간 복잡도가 $O(n^2)$이나 걸리므로 분할 정복을 이용하여 효율성을 높일 수 있다. 

1. 점들을 x좌표에 따라 오름차순으로 정렬한다.
2. x좌표를 기준으로 배열을 반반으로 분할한다. ($base case: n \le (2$ 이상의 자연수$)$)
3. 왼쪽에서의 답과 오른쪽에서의 답을 각각 $DL, DR$ 이라 하자. 그리고 $D = min(DL, DR)$ 을 구하면서 재귀적으로 합치면 된다.

하지만 왼쪽 영역의 점과 오른쪽 영역의 점이 합쳐진 경우가 존재하여 D가 답이 아닐 가능성이 있다. 그렇다고 왼쪽의 모든 점과 오른쪽의 모든 점끼리 비교할 수는 없다. 이를 해결하기 위해서 밴드라는 아이디어를 생각해보자. 가상의 수직선을 긋고, 왼쪽으로 D, 오른쪽으로 D만큼씩 이동하여 경계를 만들어서 밴드를 생성한다. 이 밴드 내에서만 왼쪽 점 하나, 오른쪽 점 하나를 비교하면 D보다 작은 경우를 쉽게 찾을 수 있다.

 

2. $O(nlog^2n)$ 풀이

1. 밴드의 내부에 한 변의 길이가 2D인 정사각형을 생각하자. 여기서 찾고자 하는 것은 어떤 점 p에 대해서 D보다 가까운 점이 있는지이다. p는 정사각형 오른쪽 영역의 가운데 높이에 위치한다고 가정하자.
2. 밴드 내의 점들끼리 거리는 D보다 커야 되므로 p와 비교해야할 점은 최대 5개이다.
3. 이를 일반화하면 각 밴드 내의 점들이 모두 5개씩 비교를 해서 D보다 작은 거리가 있는지를 찾아야 한다. 밴드 안에 있는 모든 점들을 y좌표에 따라 오름차순 정렬을 한 뒤 왼쪽 오른쪽 영역 구분 없이 본인보다 위에 있는 5개의 점을 선택해서 비교하면 된다. 여기서 D보다 짧은 거리가 있으면 그게 답이고, 없으면 D가 답이다.

 

3. $O(nlogn)$ 풀이

밴드를 만든 후, 밴드 안에 있는 것만 보는 것이 아니라 모든 점들을 y좌표에 따라 오름차순 정렬을 한 뒤 5개의 점을 선택해서 비교한다. 이렇게 하면 밴드 내에서 D보다 작은 거리가 있는지 찾는 작업은 똑같이 $O(n)$ 만 걸린다. 왼쪽 영역에서 y좌표 정렬, 오른쪽 영역에서 y좌표 정렬된 것끼리 다시 합칠 때는 Merge를 하므로 이 때 $O(logn)$ 만 걸리게 되어 총 시간은 $O(n\log n)$이 걸린다. 3번 풀이에서는 정렬하는 시간이 $O(n\log n)$이 소요되었지만 여기서는 Merge를 통해 시간을 $log n$만큼 줄여서 최종적으로 $O(n\log n)$의 시간만에 Closest Pair를 구할 수 있다.

 

4. Plane Sweeping 풀이

점들을 x좌표 오름차순으로 정렬하고, 수직선이 점들을 지나가면서 지금까지 본 것들 중에서 가장 가까운 거리를 수직선에 저장한다. (수직선에는 밴드의 점들이 y좌표 순으로 정렬되어 AVL 트리 / Red black 트리 형태로 저장된다.)