[WEEK02] 백준 2261 가장 가까운 두 점

문제

2차원 평면상에 n개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 있다.

출력

첫째 줄에 가장 가까운 두 점의 거리의 제곱을 출력한다.

풀이

분할정복을 사용하여 풀어야 한다는건 알았지만, 어떻게 접근해야할지 도저히 생각이 안났다.
다른 사람의 코드를 보고 이해한바로는 다음과 같다.

입력받은 좌표들을 x 좌표 기준으로 오름차순 정렬을 한뒤, 좌우로 절반씩 영역을 쪼개간다.
바텀업 방식으로 보자면 마지막 영역에서는 점1개 또는 점2개가 나오게 될것이다.

점 1개일 때의 거리는 sys.maxsize로 반환
점 2개일 때의 거리는 dist 함수를 이용하여 두 점 사이의 거리를 반환해주었다.

def dist(p1, p2):
    return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2

이제 이 값을 기준으로 해당 영역을 호출해주었던 상위 영역으로 돌아와
비교를 해줄거다.

바로 거리를 계산해주어 가져온 값과 비교를 하는것이 아닌 눈대중으로 봐도 이건 멀다 싶은것은 다 제외해준다.
눈대중 검사라 표현하겠다. 눈대중 검사는 점들간의 거리를 x좌표만의 크기 차이를 검사해주고 이 값이 리턴 받은 값보다 작은 점들만 후보군에 올려주고 후보군들끼리에서도 y좌표만의 크기 차이를 검사해 작을 때에만 dist함수를 이용하여 거리를 계산해주고 값을 갱신해준다.

코드는 다음과 같다.

def func(a, left, right):

    if left == right:
        return sys.maxsize
    if right - left == 1:
        return dist(a[left], a[right])
    
    mid = (left + right) // 2
    min_dist = min(func(a, left, mid - 1), func(a, mid + 1, right))

    target_pos_li = []
    for i in range(left, right + 1):
        if (a[mid][0] - a[i][0]) ** 2 < min_dist:
            target_pos_li.append(a[i])

    target_pos_li = sorted(target_pos_li, key = lambda x: x[1])
    
    t = len(target_pos_li)
    for i in range(t - 1):
        for j in range(i + 1, t):
            if (target_pos_li[i][1] - target_pos_li[j][1]) ** 2 < min_dist:
                min_dist = min(min_dist, dist(target_pos_li[i], target_pos_li[j]))
            else:
                break

    return min_dist

처음에는 영역을 A, B로 나눈다 치면 A에 있는 점과 B에 있는 점 사이의 거리는 어떻게 비교해주는거지라는 의문이 들었지만 직접 그려보고 A, B를 나눠도 A, B로 나누라 호출해 준 함수에서 결국 계산이 된다라는 것을 알게되었다.

정리하자면 이렇다.

• 분할정복을 이용하여 비교군이 될 거리를 가지고 올라온다
• 이 거리를 가지고 정확한 거리 계산이 아닌 x축 간이 검사를 통해 더 가까운 거리가 나올 가능성을 가지고 있는 후보좌표들을 저장한다.
• 후보좌표들끼리의 y축 간이 검사를 한 번더 진행한다.
• 모든 검사를 통과한 좌표들끼리의 실제 거리 계산을 통해 갱신한다.

전체코드

import sys

# 바텀업 방식으로 보면 이미 2개의 좌표 거리 부터 해서 최소 거리를 가지고 올라옴
# 나중에 실행되는 함수에서는 이 거리와 비교하여 맡고있는 영역에서 2개씩 뽑아 바로 거리 계산을 하는게 아닌
# x 좌표 거리만 봤을 때 최소 dist보다 멀면 거르고, dist보다 가까우면 일단 후보군에 올림
# 후보군에 올라온 좌표 리스트를 y축 정렬해서 y축 거리로만 비교 했을 때 dist보다 가까우면 그제서야 제대로된 거리 계산을 해주고 min()

# 요약: 눈대중으로 봐도 먼 좌표사이의 거리는 후보군 탈락
#       후보군에 올라온 것들을 y좌표 기준으로 눈대중 검사하고 통과한 좌표들에 한해서만 실제 거리 계산

def dist(p1, p2):
    return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2

def func(a, left, right):

    if left == right:
        return sys.maxsize
    if right - left == 1:
        return dist(a[left], a[right])
    
    mid = (left + right) // 2
    min_dist = min(func(a, left, mid - 1), func(a, mid + 1, right))

    target_pos_li = []
    for i in range(left, right + 1):
        if (a[mid][0] - a[i][0]) ** 2 < min_dist:
            target_pos_li.append(a[i])

    target_pos_li = sorted(target_pos_li, key = lambda x: x[1])
    
    t = len(target_pos_li)
    for i in range(t - 1):
        for j in range(i + 1, t):
            if (target_pos_li[i][1] - target_pos_li[j][1]) ** 2 < min_dist:
                min_dist = min(min_dist, dist(target_pos_li[i], target_pos_li[j]))
            else:
                break

    return min_dist


n = int(input())
pos_li = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
pos_li = sorted(pos_li)

print(func(pos_li, 0, n - 1))