[DevLog][Baekjoon] 2261: 가장 가까운 두 점

01) 문제

2차원 평면상에 n개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오. 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 있다.

예제 입/출력

4
0 0
10 10
0 10
10 0
# output is 100

02) 풀이

1. 평면을 분할한다
2. 분할된 평면에서 최소 거리를 찾는다
3. 서로 분할되어 있는 점들 중에서 최소 거리가 될 수 있는 점들만 탐색하여 최소 거리를 갱신한다.

이전 알고리즘 수업에서 분명히 접했던 문제인데도 바로 구현이 떠오르지 않았다. 위와 같은 흐름으로 divide/combine 하면 되겠구나 하는 생각은 들었지만, 3번 combine 단계를 어떻게 구현할 수 있을지 고민이 되었다. (이래서 기억에 의존해 풀면 안 된다.)

처음에는 left와 right에서 각각 y좌표의 절댓값이 가장 작은 두 점 a, b를 선택해, 이의 x값을 기준으로 사이에 있는 점만 탐색하면 어떨까? 하는 생각이 들었다. 당연히 틀렸다. 아래와 같은 반례가 존재한다.

결국 교재를 보고, combine의 접근법을 알게 되었다. 최소 거리를 찾은 후, mid의 x좌표를 기준으로 x좌표가 +/-d 인 경우에만 검색의 범위가 된다. 만약 x좌표가 경계선에서 이미 최소거리 d를 초과하여 떨어져 있다면 어떤 경우에도 다른 쪽에 있는 점과 최소거리를 이룰 수 없다.

<그림 1>의 L, R에서 최소 거리를 각각 찾은 후, 이를 d = min(dL, dR) 라고 한다. 중간에 있는 점의 범위는 그림과 같이 M이 된다. 이 중간 영역의 점들은 이중 반복문을 사용하여 최단거리를 계산해보고, 최솟값을 찾아 갱신해주어야 한다.
이 때, 만약 중간 영역의 점들이 y좌표를 기준으로 정렬되어 있다면, 검색 시간을 줄일 수 있다. (정확히는 검색이 필요 없는 경우를 처리해줄 수 있다.) 만약 i점과 j점의 y좌표 Yi, Yj의 차가 현재까지 갱신된 최소거리 d보다 큰 경우, Xi, Xj의 값에 상관없이 두 점의 거리는 항상 d보다 크거나 같게 된다.
$\ distance = \sqrt{(X_i - X_j)^2 + (Y_i - Y_j)^2} $

따라서 다음과 같은 방법을 적용할 수 있다.

for i in 0 to n-1:
  for j in i+1 to n:
    if j.y - i.y >= minD:
      break
    else minD = min(minD, distance(i, j)) # update

시행착오: 내장함수의 사용 시 주의 🚨

위와 같이 코드를 작성했는데, 이번엔 '시간 초과'가 뜨고 말았다. 중간 영역의 범위 인덱스를 구하는 과정에서 y좌표를 기준으로 내림차순 정렬을 하고 싶었나보다. sort(key, reversed=True) 를 설정하는 바람에 어이없게도 시간 리밋을 넘어버렸다. 머릿속에서 생각한 과정을 아무 생각 없이 코드로 작성했기에, 굳이 필요도 없는 역정렬 옵션을 걸어 준 것이다. 또, 정렬을 역방향으로 하는 것이 더 오래 걸릴 것이라는 생각을 하지 못했는데, 실제로는 reversed=True 옵션이 인풋이 커지는 경우 성능에 영향을 줄 수 있다고 한다. 시간 또는 메모리 초과의 순기능은 평소에 아무 생각 없이 쓰던 내장함수의 작동 방식에 대해 조금이나마 관심을 갖고 찾아보게 만든다는 점인 것 같다.

03) 코드 (파이썬)

# Closest Pair
import sys
import math


def distance(d1: tuple, d2: tuple):  # 거리 제곱
    return (d1[0]-d2[0])**2 + (d1[1]-d2[1])**2


def closest_pair(s, e):
    global minD
    if e - s == 1:
        return
    if e - s == 2:
        d = distance(D[s], D[e-1])
        if minD == None or minD > d:
            minD = d
        return

    # x좌표의 mid값 구하기
    mid = (s + e) // 2

    closest_pair(s, mid)
    closest_pair(mid, e)
    d = minD

    # mid-d < x < mid+d 점 (중간 영역) 조사
    for i in range(mid, s-1, -1):
        if D[mid][0] - D[i][0] > math.sqrt(d):
            break
    for j in range(mid, e):
        if D[j][0] - D[mid][0] > math.sqrt(d):
            break

    # i~j 중간 영역에서의 최근접점 조사
    mids = sorted(D[i:j+1], key=lambda d: d[1])
    for p in range(len(mids)-1):
        for q in range(p+1, len(mids)):
            if mids[q][1] - mids[p][1] >= math.sqrt(d):
                break
            minD = min(minD, distance(mids[q], mids[p]))

    return


# 입력을 받음
N = int(input())
D = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
minD = None

# D배열의 x좌표값을 기준으로 정렬
D.sort(key=lambda d: d[0])

# 재귀 호출
closest_pair(0, N)
print(minD)

어렵다..파이팅