가장 가까운 두 점 찾기

이 문제는 주어진 평면 상의 여러 점 중 가장 가까운 두 점을 찾는 문제입니다. 일반적인 무차별 대입 방법으로 해결할 경우 시간 복잡도가 $$O(n^2)$$이지만, 분할 정복을 사용해 $$O(n \log n)$$으로 최적화할 수 있습니다.

풀이 접근:

• 1️⃣ 주어진 점들을 x 좌표 기준으로 정렬한 후 분할합니다.
• 2️⃣ 좌측 절반과 우측 절반의 가장 가까운 점 쌍을 각각 찾고, 더 작은 거리를 선택합니다.
• 3️⃣ 중간 구간에 위치한 점들 사이의 최소 거리를 구하고, 좌우에서 찾은 거리와 비교하여 최종 답을 도출합니다.

Python 코드 예제:
import math

# 거리 계산 함수
def distance(p1, p2):
    return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)

# 무차별 대입을 통해 최소 거리 계산
def brute_force(points):
    min_dist = float('inf')
    n = len(points)
    for i in range(n - 1):
        for j in range(i + 1, n):
            min_dist = min(min_dist, distance(points[i], points[j]))
    return min_dist

# 중간에 위치한 점들 사이에서 최소 거리 계산
def closest_in_strip(strip, d):
    min_dist = d
    strip.sort(key=lambda p: p[1])  # y 좌표 기준으로 정렬

    for i in range(len(strip)):
        for j in range(i + 1, len(strip)):
            if (strip[j][1] - strip[i][1]) < min_dist:
                min_dist = min(min_dist, distance(strip[i], strip[j]))
            else:
                break
    return min_dist

# 분할 정복을 사용한 최단 거리 계산
def closest_pair(points):
    n = len(points)
    if n <= 3:
        return brute_force(points)
    
    mid = n // 2
    mid_point = points[mid]

    dl = closest_pair(points[:mid])
    dr = closest_pair(points[mid:])
    d = min(dl, dr)

    # 중간 경계에 있는 점들만 선택
    strip = [p for p in points if abs(p[0] - mid_point[0]) < d]
    return min(d, closest_in_strip(strip, d))

# 최단 거리 계산
def find_closest_pair(points):
    points.sort()
    return closest_pair(points)

# 예제 사용
points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
print(find_closest_pair(points))  # 출력: 가장 가까운 두 점 간의 거리
        

설명: find_closest_pair 함수는 주어진 점들을 x 좌표로 정렬한 후 분할 정복을 사용해 최소 거리를 계산합니다. 각 단계마다 좌측과 우측 구간을 분할하여 중간 지점에서의 최소 거리를 계산합니다.