백준 2261 <가장 가까운 두 점> Python

https://www.acmicpc.net/problem/2261

---

해당 문제는 전형적인 Closest Pair 알고리즘에 관한 문제입니다.

 

일반적으로 아래의 과정을 거치게 됩니다.

 

0. 점들을 x 값 기준으로 정렬

1. 범위를 분할

  1.1. 범위 내에 점이 1개면 max 를 리턴

  1.2. 범위 내에 점이 2개면 해당 길이를 리턴

 

2. 범위 내에 점이 3 개 이상이면 위의 과정에서 나온 최솟값 + 분할된 두 범위 사이의 교차 길이 계산

  2.1 교차길이는 현재 최솟값보다 길면 계산한 필요가 없음

        -> 중앙에서 최솟값을 더하고 빼준 x 범위 외부의 점은 계산할 필요가 없음

        (x 범위가 해당 값 외부면 무조건 교차 길이가 최솟값보다 길기 때문)

  2.2 해당 범위의 값들을 y 값 기준으로 정렬해 순회하며 길이 구해주기

        y 값 기준으로 순회할 때에도 y 길이가 최솟값보다 길면 계산할 필요 없기 때문에

        이를 넘어서는 순간 다음 좌표로 이동

 

점의 개수가 많은 경우 O(N^2) 은 말도 안되는 시간이 소요되기 때문에 최소한으로 계산해야 하는 Pair 를 선별하는 과정이라고 볼 수 있습니다.

 

---

import sys

input = sys.stdin.readline
      

# 거리 계산
def cal_dist(p1, p2):
    dx = p1[0] - p2[0]
    dy = p1[1] - p2[1]

    return dx**2 + dy**2


# 분할 정복
def divide(points, left, right):
    # 범위내 거리를 구할 수 없으면
    if left >= right:
        return float('inf')
    
    # 범위내 거리가 하나면
    elif right - left == 1:
        return cal_dist(points[right], points[left])
    
    # 중앙
    half = (left + right) // 2
    # 최소 거리
    min_dist = min(divide(points, left, half), divide(points, half, right))
    # 중심부터 최소거리만큼 떨어진 범위 내부의 점들 구하기
    candid_list = [points[i] for i in range(left, right+1) 
                   if (points[half][0] - points[i][0])**2 < min_dist]
    # y 정렬
    candid_list.sort(key=lambda x:x[1])
    # 순회
    for l in range(len(candid_list)-1):
        for r in range(l+1, len(candid_list)):
            # y 거리가 최소 거리보다 길면 패스
            if (candid_list[l][1] - candid_list[r][1])**2 < min_dist:
                # 최단거리 갱신
                min_dist = min(min_dist, cal_dist(candid_list[l], candid_list[r]))

            else:
                break

    return min_dist 


def solution(n, points):
    # x 기준으로 정렬
    points.sort(key=lambda x:x[0])
    # 분할 정복
    print(divide(points, 0, n-1))


# 입력
n = int(input().strip())
points = [list(map(int, input().strip().split())) for _ in range(n)]

solution(n, points)