[Python - Divide & Conquer, Sweeping] 2261 가장 가까운 두 점

📌 문제

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

📌 입력

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

📌 출력

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

📌 문제 풀이

👨‍🏫 접근

너무 어려웠다. 일단 이걸 어떻게 분할해서 풀어야할지가 고민이 되었다. 그런데 생각보다 분할은 그렇게 어려운 게 아니었다.

 

이 문제는 3번의 탐색 과정을 거친다.

 

좌표들을 일단 x값을 기반으로 정렬을 해준 다음, 첫 좌표와 끝 좌표의 중간을 구해준다.

첫 번째 탐색은 첫 번째 좌표부터 중간 좌표까지 탐색하며 최소 거리을 찾는다. 두 번째 탐색은 중간 좌표부터 끝 좌표까지 탐색하며 최소 거리를 구한다.

 

마지막으로 처음부터 끝까지 중간좌표와 차이를 통해 값을 구한다. 이때 첫 번째와 두 번째 탐색에서의 최솟값과 비교하여 더 작은 값을 리스트에 저장해둔다. 그 이후, 그 리스트에서 y값을 다시 비교하여 최종적으로 가장 짧은 거리를 찾는 것이다.

 

이것을 분할정복으로 해서 풀어주는 것이 핵심이다. 완전탐색으로 하나하나 구하려면 O(n²)의 시간 복잡도가 소요되는데, 여기서 n이 최대 10⁶이어서 10⁹를 훌쩍 넘기 때문에 분할정복으로 풀어주어야 한다.

👨‍🏫 문제 풀이

📄 전체 코드

import sys
input = sys.stdin.readline


def calc(c1, c2):
    return (c1[0] - c2[0]) ** 2 + (c1[1] - c2[1]) ** 2


n = int(input())
graph = sorted([tuple(map(int, input().split())) for _ in range(n)])


def dq(left, right):
    if left == right:
        return float('inf')
    elif right - left == 1:
        return calc(graph[left], graph[right])

    mid = (left + right) // 2
    ans = min(dq(left, mid), dq(mid + 1, right))

    coor = []
    for i in range(left, right + 1):
        d = graph[i][0] - graph[mid][0]
        if d ** 2 < ans:
            coor.append(graph[i])

    coor.sort(key=lambda x: x[1])

    for i in range(len(coor) - 1):
        for j in range(i + 1, len(coor)):
            d = coor[i][1] - coor[j][1]
            if d ** 2 < ans:
                ans = min(ans, calc(coor[i], coor[j]))
            else:
                break

    return ans


print(dq(0, n - 1))

📄 준비

import sys
input = sys.stdin.readline

def calc(c1, c2):
    return (c1[0] - c2[0]) ** 2 + (c1[1] - c2[1]) ** 2

n = int(input())
graph = sorted([tuple(map(int, input().split())) for _ in range(n)])

거리 연산이 필요해서 함수로 정리해주고, 각 좌표들을 x값을 기준으로 정렬한다.

📄 풀이

def dq(left, right):
    if left == right:
        return float('inf')
    elif right - left == 1:
        return calc(graph[left], graph[right])

    mid = (left + right) // 2
    ans = min(dq(left, mid), dq(mid + 1, right))

    coor = []
    for i in range(left, right + 1):
        d = graph[i][0] - graph[mid][0]
        if d ** 2 < ans:
            coor.append(graph[i])

    coor.sort(key=lambda x: x[1])

    for i in range(len(coor) - 1):
        for j in range(i + 1, len(coor)):
            d = coor[i][1] - coor[j][1]
            if d ** 2 < ans:
                ans = min(ans, calc(coor[i], coor[j]))
            else:
                break

    return ans


print(dq(0, n - 1))

각 탐색에서 거리값을 구하는 기준은 최종적으로 좌표가 2개만 남았을 때이다. 시작과 끝이 같다면 그것은 점이 하나인 것이므로, 무한을 반환해준다. 이렇게 좌표가 1개만 있는 경우는 앞선 탐색에서 좌표가 3개가 존재하여 1개 2개로 분할했기 때문이다.

 

중간을 기준으로 분할하여 최소 거리를 찾아냈다면, 이제 다시 중간 좌표를 기준으로 처음부터 끝까지 다시 탐색해준다. 그 이후에 y좌표를 통해 비교해나가면서 최종적으로 답을 찾아낸다. 만약 처음부터 끝까지 탐색하면서 좌 우 범위의 탐색에서의 최솟값보다 작은 값이 없다면 그 이후의 반복에서는 처리될 것이 없기 때문에 그대로 반복문을 탈출한다. 그 이후에 최솟값을 출력하지 때문에 크게 문제될 것이 없다.

📌 총평

 

사실 분할이 될까 생각해서 안 했었는데, 차라리 일단 해보고 안되는지 확인하는 게 낫겠다.