[Python] 백준 2261 가장 가까운 두 점

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

2261번: 가장 가까운 두 점

이번에 풀 문제는 가장 가까운 두 점이다.

2차원 평면상에 n개의 점이 주어졌을 때, 가장 가까운 두 점의 거리를 구하는 간단한 문제이다. 설명은 아주 간단하지만 풀이는 그렇지 않다! n의 범위가 최대 100,000 이기 때문에 완전 탐색으로 문제를 풀게 되면 시간 초과를 피하지 못한다... 

 

나는 이 문제를 분할 정복 방식으로 풀었는데, 풀이가 이전에 풀었던 히스토그램에서 가장 큰 직사각형 찾기 문제의 분할 정복 풀이와 비슷한 점이 많으니 참고하면 좋다! 

 

https://codable.tistory.com/1

[Python] 백준 6549번 히스토그램에서 가장 큰 직사각형

 

 

문제 풀이

 

 

예제 그림

기본적으로 분할 정복을 활용하는 풀이이기 때문에 어떤 상황에서 분할을 진행할 것인지 정해야 한다. 보통 가운데를 기준으로 분할을 진행하기 때문에 이 문제에서도 가운데를 기준으로 분할을 진행하였다. 여기서 가운데란 모든 점들을 x 좌표를 기준으로 오름차순 정렬했을 때, 배열의 가운데에 있는 점을 말한다. 

그림의 점은 총 19개이고, 10번째 점을 기준으로 분할을 진행하기 때문에 분할을 한 결과는 다음과 같을 것이다. 

 

첫번째 분할 이후

위와 같은 방식으로 계속해서 분할을 진행한다. 분할은 더 이상 영역이 나누어지지 않을 때까지 반복하며, 나눌 수 없는 영역이 되었으면 영역 내의 점들의 거리를 계산하여 최솟값을 반환한다. 

 

위의 그림처럼 점이 총 19개 있는 상황에서 분할은 다음과 같이 진행될 것이다. 

 

분할 결과

마지막 결과들을 보면 크기가 2 또는 3인 것을 볼 수 있는데, 이는 영역에 점이 하나 밖에 남지 않아 거리 계산을 하지 못하는 경우를 방지하기 위함이다. 따라서 분할한 범위의 크기가 3 이하인 경우에는 더 이상 분할을 진행하지 않고 영역 내의 점들끼리 거리 계산을 진행해 준다. 

 

영역 내의 점들끼리 최소 거리를 계산해주는 방식은 완전 탐색으로 구현하였으며, 코드는 다음과 같다.

 

def compute_min_dist(start, end):
    min_dist = int(1e10)
    for i in range(start, end-1):
        for j in range(i+1, end):
            dist = (points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2
            min_dist = min(min_dist, dist)
    return min_dist

 

점들의 좌표의 최대 범위가 -10,000 부터 10,000까지이기 때문에, 두 점 사이 거리가 최대인 경우는 800,000,000이다. 따라서 초기 min_dist 값을 거리의 최댓값보다 큰 $10^10$으로 설정하였다. 

 

이제 왼쪽과 오른쪽 영역으로 분할을 하고, 각각의 영역에서 두 점 사이 거리의 최솟값을 구해보았다. 하지만 그림 상에서 가장 가까운 두 점은 가운데 선을 걸쳐서 존재하는 것을 확인할 수 있다. 

 

이전 히스토그램 문제의 분할 방식 풀이법에서도 왼쪽 영역과 오른쪽 영역에서의 최댓값을 구한 뒤, 가운데를 걸친 영역을 다시 조사하여 최댓값을 갱신해주었다. 이와 마찬가지로 이 문제에서도 왼쪽 영역과 오른쪽 영역에서의 최솟값을 구하고, 왼쪽 영역의 점과 오른쪽 영역의 점들을 조사하여 최솟값을 갱신해주어야 한다. 

 

단순한 방법으로 왼쪽의 모든 점들과 오른쪽의 모든 점들 사이의 거리를 계산하는 방법도 있겠지만, 그렇게 구현을 하면 시간복잡도가 $O(n^2 log n)$으로 문제의 조건을 만족하지 못하게 된다. 

따라서 우리는 특정 영역의 점들에 대해서만 검사를 진행한다. 

 

왼쪽 영역의 최솟값과 오른쪽 영역의 최솟값을 구한 상태라고 가정하자. 우리는 이제 왼쪽 영역의 최솟값과 오른쪽 영역의 최솟값을 비교하여 더 짧은 거리를 min_dist 라는 변수에 저장한다. 여기까지의 코드를 보면 다음과 같다.

 

def find_min_dist(start, end):
    size = end - start
    if size < 3:
        return compute_min_dist(start, end)
    
    mid = (start + end) // 2
    
    left = find_min_dist(start, mid)
    right = find_min_dist(mid, end)
    
    min_dist = min(left, right)

현재까지 구한 거리의 최솟값이 min_dist 이기때문에, 분할을 진행한 선을 기준으로 min_dist 보다 멀리 떨어진 점은 조사를 할 필요가 없다. 이를 그림으로 나타내면 다음과 같다.

 

그림에서 노란 부분만 검사를 진행하는데, 최대한 시간을 줄이기 위해 노란 영역에 속하는 점들을 y 좌표를 기준으로 오름차순 정렬을 해준다. 

 

# find_min_dist

    check_point = []
    
    divide_x = points[mid][0]
    for i in range(start, end):
        if (points[i][0] - divide_x)**2 <= min_dist:
            check_point.append(points[i])
    check_point.sort(key=lambda x:x[1])

 

이후 가장 아래에 있는 점부터 영역 내의 다른 점들과의 거리를 계산해 주는데, 만약 y 좌표의 차이가 min_dist 보다 크다면 이후의 점들도 거리가 min_dist 보다는 커지기 때문에 반복문을 종료한다. 이렇게 반복문이 종료되기 전까지 다른 점들과의 거리를 구하며 min_dist를 갱신한다. 

 

첫 번째 점은 min_dist 거리 이내에 점이 없기 때문에 반복문이 바로 종료된다.

 

두 번째 점은 영역 내에 점이 존재하고, 그 점과의 거리가 현재의 min_dist 보다 짧기 때문에 min_dist 값을 갱신해 준다. 

 

위와 같은 과정을 반복하면 거리의 최솟값을 찾을 수 있다! 

 

전체적인 코드는 아래와 같다.

 

import sys

input = sys.stdin.readline

n = int(input())

points = []

for _ in range(n):
    x, y = map(int, input().split())
    points.append((x, y))
    
points.sort()

def compute_min_dist(start, end):
    min_dist = int(1e10)
    for i in range(start, end-1):
        for j in range(i+1, end):
            dist = (points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2
            min_dist = min(min_dist, dist)
    return min_dist

def find_min_dist(start, end):
    size = end - start
    if size < 3:
        return compute_min_dist(start, end)
    
    mid = (start + end) // 2
    
    left = find_min_dist(start, mid)
    right = find_min_dist(mid, end)
    
    min_dist = min(left, right)
    
    check_point = []
    divide_x = points[mid][0]
    for i in range(start, end):
        if (points[i][0] - divide_x)**2 <= min_dist:
            check_point.append(points[i])
    check_point.sort(key=lambda x:x[1])
    
    
    for i in range(len(check_point)):
        now = check_point[i]
        for j in range(i+1, len(check_point)):
            compare = check_point[j]
            if (compare[1] - now[1])**2 >= min_dist:
                break
            dist = (now[0] - compare[0])**2 + (now[1] - compare[1])**2
            min_dist = min(min_dist, dist)
    
    return min_dist 

print(find_min_dist(0, n))