평면에 점이 흩어져 있을 때 가장 가까운 두 점을 찾는 문제다.
전부 비교하기
coords = [(random.randint(-100, 100), random.randint(-100, 100)) for _ in range(500)]
coords.sort()
n = len(coords)
min = float('inf')
pair = ()
for i in range(n):
for j in range(i + 1, n):
length = math.hypot((coords[j][0] - coords[i][0]), (coords[j][1] - coords[i][1]))
if length < min:
min = length
pair = (coords[i], coords[j])
math.hypot 이 제곱근까지 해준다. 거리를 비교만 할 거라면 제곱근을 빼고 제곱 상태로 비교해도 되는데 여기서는 실제 거리를 답으로 출력하므로 그대로 뒀다.
coords.sort() 를 해두었지만 완전탐색에서는 쓰이지 않는다. 다음 버전을 염두에 둔 것으로 보인다.
시험 데이터에 문제가 있다
점을 -100 부터 100 까지의 정수 격자에서 뽑는데, 격자점이 40401개뿐이다. 거기에 500개를 던지면 같은 자리에 두 점이 떨어질 확률이 높다.
시드를 200번 바꿔 돌려보니 186번은 겹치는 점이 생겼다. 그러면 최소 거리가 0이 되고 어느 방법을 써도 답이 0이다. 알고리즘을 비교하기에 좋은 입력이 아니다.
50개로 줄이면 200번 중 6번만 겹친다.
한 번 나누고 경계만 다시 보기
median = len(coords) // 2
coords_left = coords[:median]
coords_right = coords[median:]
res_left = closet_pair(coords_left)
res_right = closet_pair(coords_right)
min_total = min(res_left[0], res_right[0])
coords_boun = [i for i in coords
if i[0] >= coords[median][0] - min_total
and i[0] <= coords[median][0] + min_total]
res_boun = closet_pair(coords_boun)
ans = min(res_left, res_right, res_boun, key=lambda n:n[0])
x 기준으로 정렬하고 반으로 자른다. 왼쪽끼리, 오른쪽끼리 최소 거리를 구한다.
여기서 놓치는 게 있다. 가장 가까운 두 점이 경계를 사이에 두고 갈라져 있을 수 있다. 그래서 경계선에서 좌우로 min_total 만큼의 띠를 잡아 그 안의 점들을 다시 확인한다.
띠의 폭이 min_total 인 이유가 핵심이다. 이미 min_total 이라는 답을 갖고 있으므로, 그보다 가까운 쌍이 있다면 두 점 모두 경계에서 min_total 안에 있어야 한다. 그 밖의 점은 볼 필요가 없다.
아직 분할정복이 아니다
이름은 divide and conquer.py 인데 실제로는 한 번만 나눈다. closet_pair 는 전달받은 점들을 완전탐색한다.
제대로 하려면 closet_pair 가 자기 자신을 다시 불러야 한다. 반으로, 다시 반으로 나눠 내려가다 점이 세 개쯤 남으면 그때 직접 비교한다.
지금 형태로는 절반 크기의 완전탐색을 두 번에 띠 하나를 더 하는 것이라 비교 횟수가 절반 정도로 준다. 재귀로 끝까지 내려가야 차수 자체가 바뀐다.
띠 안의 점을 y로 정렬해 앞뒤 몇 개만 비교하는 부분도 없다. 지금은 띠 안을 완전탐색하는데, 점이 몰려 있으면 띠에 대부분이 들어와 이득이 사라진다.