[python] 백준 2261 :: 가장 가까운 두 점 (분할 정복)

[가장 가까운 두 점]

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

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

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

💡 참고한 블로그 👉🏻 codable

1. 입력 받아서 x좌표를 기준으로 정렬한다.

• 점이 뒤죽박죽으로 주어지니까, 일단 정렬부터 하고 보자..

# n개의 점을 입력 받아 2차원 리스트로 저장
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

arr.sort()  # x좌표를 기준으로 정렬

2. 두 점 사이를 구한다.

• 점이 음수일 수 있으므로 거리를 구하기 위해서는
  (x 좌표 차이의 제곱 + y 좌표 차이의 제곱) ** 1/2 요로케 해주면 된다.
  문제에서 거리의 제곱을 출력하라고 했으니 여기서 ** 1/2는 노놉!

def get_dist(a, b):  # 두 점 사이의 거리를 구하는 함수
    return (a[0]-b[0])**2+(a[1]-b[1])**2

3. 점의 개수에 따라 분기한다.

• 자 이제 최솟값 구하기 스타또-!
• 시작점과 끝점을 인자로 받아서 분할 정복으로 풀 것이다.
• start와 end의 차이가 0 또는 1이 될 때까지 쪼갤거임

start와 end의 차이가 0

• 반띵씩 줄어들다보면 같은 값이 시작점과 끝점으로 주어질 수도 있다.
  이때는 거리를 계산할 수 없으니 결과값에 영향을 주지 않게 sys.maxsize를 때려버린당

def get_min(start, end):
    if start == end:  # 점이 하나인 경우, 최대값 반환
        return sys.maxsize

start와 end의 차이가 1

• 점이 두 개일 때는 위에서 만들어 둔 함수로 두 점 사이의 거리를 구한다.

    if end - start == 1:  # 점이 두 개인 경우, 두 점 사이의 거리 반환
        return get_dist(arr[start], arr[end])

start와 end의 차이가 0도 아니고 1도 아님

• 차이가 0이나 1이 되게 쪼개주자

    mid = (start + end) // 2  # 중간 지점 계산
    
    # 왼쪽 절반과 오른쪽 절반을 각각 재귀적으로 호출
    min_dist = min(get_min(start, mid), get_min(mid, end))

4. mid 근처를 검증한다.

• 쪼개지는 부분에 절묘하게 답이 존재할 수도 있다.
  그래서 쪼개지는 부분도 검증해줘야 한다. 🙁😠

• 위에서 일단 min_dist를 구했으니까,
  쪼개진 지점인 arr[mid]를 중심으로 왼쪽 오른쪽으로 -min_dist ~ +min_dist 범위 안에 드는 점들만 찾아서 candidates에 모은다.

• 범위 안에 드는 점들만 찾기 👉🏻(arr[mid][0] - arr[i][0])**2 < min_dist
  💡 이 거리가 제곱되어있는 값이라는 것 잊지말자

    # 가운데 점(mid)을 기준으로 거리가 min_dist보다 작은 점들을 candidates 리스트에 추가
    candidates = []
    for i in range(start, end+1):
        if (arr[mid][0] - arr[i][0])**2 < min_dist:
            candidates.append(arr[i])

• 범위를 또 줄여주기 위해서 y좌표를 기준으로 정렬한다.

    # candidates 리스트를 y좌표를 기준으로 정렬
    candidates.sort(key=lambda x: x[1])

• 아래점에서 위에 위치하는 애들만 계산을 해본다.

    # candidates 리스트 내에서 최소 거리를 구함
    for i in range(len(candidates)-1):
        for j in range(i+1, len(candidates)):

• 위에서 candidates를 만들 때 했던 것처럼, y좌표도 차이의 제곱이 min_dist를 넘어가면 반복을 멈춘다. (어차피 더 멀어서 볼 것도 없음😋)

            # y좌표 차이가 min_dist보다 작은 경우에만 최소 거리 계산
            if (candidates[i][1] - candidates[j][1])**2 < min_dist:
                min_dist = min(min_dist, get_dist(
                    candidates[i], candidates[j]))
            else:
                break

끝😘

전체 코드

import sys
n = int(input())

# n개의 점을 입력 받아 2차원 리스트로 저장
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

arr.sort()  # x좌표를 기준으로 정렬


def get_dist(a, b):  # 두 점 사이의 거리를 구하는 함수
    return (a[0]-b[0])**2+(a[1]-b[1])**2


def get_min(start, end):
    if start == end:  # 점이 하나인 경우, 최대값 반환
        return sys.maxsize

    if end - start == 1:  # 점이 두 개인 경우, 두 점 사이의 거리 반환
        return get_dist(arr[start], arr[end])

    mid = (start + end) // 2  # 중간 지점 계산
    # 왼쪽 절반과 오른쪽 절반을 각각 재귀적으로 호출하여 최소 거리를 구함
    min_dist = min(get_min(start, mid), get_min(mid, end))

    # 가운데 점(mid)을 기준으로 거리가 min_dist보다 작은 점들을 candidates 리스트에 추가
    candidates = []
    for i in range(start, end+1):
        if (arr[mid][0] - arr[i][0])**2 < min_dist:
            candidates.append(arr[i])

    # candidates 리스트를 y좌표를 기준으로 정렬
    candidates.sort(key=lambda x: x[1])

    # candidates 리스트 내에서 최소 거리를 구함
    for i in range(len(candidates)-1):
        for j in range(i+1, len(candidates)):
            # y좌표 차이가 min_dist보다 작은 경우에만 최소 거리 계산
            if (candidates[i][1] - candidates[j][1])**2 < min_dist:
                min_dist = min(min_dist, get_dist(
                    candidates[i], candidates[j]))
            else:
                break

    return min_dist


print(get_min(0, n-1))