[🏅2 / 백준 2261 / 파이썬] 가장 가까운 두 점

 

2261번: 가장 가까운 두 점

 

문제

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

입력

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

출력

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

 

예제 입력  4 0 0 10 10 0 10 10 0

예제 출력  100

 

풀이

 

수많은 점들 중 가장 가까운 두 점 사이의 거리의 제곱을 찾는 문제이다.

 

설명에 대놓고 어려우니 검색을 추천하라고 되어 있어서 얌전히 검색을 해보았다.

보통 Closest Pair 알고리즘을 사용하는 것 같았다. (자세한 설명은 https://casterian.net/archives/92 를 참고)

 

핵심은 가지치기이다.

 

 

알고리즘을 요약하면 이렇다.

 

1. 모든 점을 x 좌표를 기준으로 정렬
2. 점들의 중앙값을 기준으로 양분할
3. 2개 까지로 분할되면 점 사이의 최소 거리를 찾고, 해당 거리보다 x좌표끼리 가까운 것만 후보 점으로 등록
4. y좌표 기준으로도 정렬하고 y좌표 차이가 최소 거리보다 낮은 것들만 대상으로 거리를 계산

 

최소 거리를 정해두고, 해당 거리보다 긴 것들은 모두 배제하는 가지치기 방식의 알고리즘이다.

 

코드를 거의 배끼듯이 한 것 같다. 문제를 풀었다기 보단 공부했다는 것에 의의를 두어야겠다.

 

import sys, random
input = sys.stdin.readline
n = int(input())
pl = [list(map(int,input().split())) for i in range(n)]

# x축 기준 정렬
pl.sort()

# 두 점 사이의 거리 계산 함수
def getDist(p1, p2):
    return (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2

def dac(start,end):
	# 점 하나의 거리는 없으니 최대값 리턴
    if start == end:
        return float('inf')
        
    # 점이 두 개 남으면 사이의 거리 리턴
    if end - start == 1:
        return getDist(pl[start],pl[end])
    
    # 분할정복 실행
    mid = (start + end)//2
    minDist = min(dac(start, mid), dac(mid,end))
    
    # x축 기준으로 후보 점들을 찾는다.
    target_pl = []
    for i in range(start, end+1):
        if (pl[mid][0] - pl[i][0])**2 < minDist:
            target_pl.append(pl[i])
            
    # y축 기준 정렬
    target_pl.sort(key=lambda x: x[1])
    
    # y축 기준으로 후보 점들 사이의 거리 비교
    t = len(target_pl)
    for i in range(t-1):
        for j in range(i+1,t):
            if (target_pl[i][1] - target_pl[j][1])**2 < minDist:
                minDist = min(minDist, getDist(target_pl[i],target_pl[j]))
            else:
                break
                # 현재 후보 점이 다음 점과 최소 거리보다 멀다면 더 볼 필요가 없음.
                # 위 처리가 없으면 시간 초과 발생
    return minDist

print(dac(0,n-1))