백준 2261 가장 가까운 두 점 파이썬

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

 

예제 입력	예제 출력
4 0 0 10 10 0 10 10 0	100

 

문제 바로가기

---

코드 구현

모든 점을 하나씩 비교하면 시간 초과가 난다. 그렇기 때문에 특정 조건을 하나 세우고, 이 조건에 부합하는 점들만 모아놓는다. 구한 점들끼리만 계산하여 가장 가까운 거리를 구해야 정해진 시간 안에 답을 얻을 수 있다.

 

두 점 사이 거리

먼저 코드의 편의성을 위해 두 점 사이 거리를 (정확히는 두 점 사이 거리의 제곱을) 구하는 함수를 만들어 따로 빼둔다.

def distance(dot1, dot2):
    return (dot1[0] - dot2[0]) ** 2 +(dot1[1] - dot2[1]) ** 2

 

X좌표 기준

먼저 X좌표를 기준으로 왼쪽과 오른쪽으로 나눠 분할 정복한다. 가운데 점을 구하고, 그 점을 기준으로 최소 거리 값을 구한다. 가운데 점과 구한 최소 거리를 기준으로 이보다 가까운 점들을 구해 따로 저장한다.

candidates = []
for i in range(start, end+1):
    if (dots[mid][0] - dots[i][0]) ** 2 < minvalue:
        candidates.append(dots[i])

 

Y좌표 기준

처음에 X좌표를 기준으로 최소 거리 값을 구했으니, 이제 Y좌표를 포함하여 최소 거리를 계산해야 한다. 구한 점들 중 현재 최소 거리보다 작은 경우에만 계산하여 최소 거리를 업데이트해 나간다.

for i in range(len(candidates)-1):
    for j in range(i+1, len(candidates)):
        if (candidates[i][1] - candidates[j][1]) ** 2 < minvalue:
            minvalue = min(minvalue, distance(candidates[i], candidates[j]))
        else:
            break

 

전체 코드

import sys
input = sys.stdin.readline

n = int(input())
dots = [list(map(int, input().split())) for _ in range(n)]

# X좌표를 기준으로 정렬
dots.sort()

# 두점 사이 거리의 제곱
def distance(dot1, dot2):
    return (dot1[0] - dot2[0]) ** 2 +(dot1[1] - dot2[1]) ** 2

def divide(start, end):
    # 만약 점이 하나라면 최대값 리턴
    if start == end:
        return sys.maxsize
    
    # 만약 점이 두개라면 두 점 사이 거리 리턴
    if end - start == 1:
        return distance(dots[start], dots[end])
    
    # 가운데 점 구해 최소 거리 값 구하기
    mid = (start + end) //2
    minvalue = min(divide(start, mid), divide(mid, end))

    # 구한 최소 거리를 기준으로 이보다 가까운 점들 구하기
    candidates = []
    for i in range(start, end+1):
        if (dots[mid][0] - dots[i][0]) ** 2 < minvalue:
            candidates.append(dots[i])

    # Y좌표를 기준으로 정렬
    dots.sort(key=lambda x: x[1])

    # 구한 점들 중 가장 가까운 점 구하기
    for i in range(len(candidates)-1):
        for j in range(i+1, len(candidates)):
            # 현재 최소 거리보다 작은 경우에만 계산하기
            if (candidates[i][1] - candidates[j][1]) ** 2 < minvalue:
                minvalue = min(minvalue, distance(candidates[i], candidates[j]))
            else:
                break

    return minvalue

print(divide(0, n-1))