백준 2261번: 가장 가까운 두 점 (Python, PyPy3)

접근

모든 점에 찾으면 안되는 것은 당연한 것이고, 이전 문제인 히스토그램 풀이 방법을 지표삼아 분할 정복 알고리즘으로 풀어보려고 굉장히 여러번 시도를 하였고, 결국 Python으로는 시간초과, PyPy3으로 시도하여 성공은 하였다.

2021.04.03 - [코딩/백준 (Python)] - 백준 6549번: 히스토그램에서 가장 큰 직사각형 - 분할 정복 (Python)

백준 6549번: 히스토그램에서 가장 큰 직사각형 - 분할 정복 (Python)

히스토그램과 비슷한 분할 정복 알고리즘을 이용하되, 양쪽에 걸쳐있는 좌표들을 한번 더 걸러주지 않으면 안된다. 먼저,

1. 중간 x값을 기준으로 왼쪽 좌표들의 거리 최소값
2. 중간 x값을 기준으로 오른쪽 좌표들의 거리 최소값
3. 중간 x값을 기준으로 양쪽에 좌표가 한개씩 있을 때 거리의 최소값

세가지 값의 최소값을 찾는데, 이 중 세번째 항목 좌표들을 적당히 걸러주지 않으면 안된다. 코드에서 그 방법을 설명하겠다.

코드

import sys

n = int(sys.stdin.readline())
points = []
for _ in range(n):
    points.append(tuple(map(int, sys.stdin.readline().split())))
points = list(set(points))  # set으로 바꿔서 중복 점들을 지운다. 중복된 점이 있을 경우 거리 최소값은 0이므로 계산을 빠르게 할 수 있다.
points.sort(key=lambda x: x[0])  # 점의 x좌표를 기준으로 오름차순 정렬


def distance(a, b):
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2


def divideandconquer(m):
    if len(m) == 2:
        return distance(m[0], m[1])
    elif len(m) == 3:
        return min(distance(m[0], m[1]), distance(m[0], m[2]), distance(m[1], m[2]))
    else:
        mid = len(m) // 2
        minimumd = min(divideandconquer(m[:mid]), divideandconquer(m[mid:]))
        # 분할정복 알고리즘을 이용하여 양쪽 구역에서 구해지는 거리 최소값을 minimumd에 저장
        # 아래로는 경계선 양쪽에 걸친 좌표들의 거리를 걸러내는 내용
        temp = []
        for i in range(len(m)):
            if (m[i][0] - m[mid][0]) ** 2 <= minimumd:  # 경계선을 기준으로 x 좌표가 최소거리보다 작은 점들만 후보군에 포함
                temp.append(m[i])
        if len(temp) >= 2:  # 후보 좌표의 개수가 1개 이하이면, 거리값이 존재하지 않음
            temp.sort(key=lambda x: x[1])  # 후보 좌표들을 y 값 기준으로 오름차순 정렬
            for i in range(len(temp) - 1):
                for j in range(i + 1, len(temp)):
                    if (temp[i][1] - temp[j][1]) ** 2 > minimumd:
                        break  # 후보 좌표 i와 j의 y좌표 거리가 최소 거리보다 클 경우 탐색 중지
                    elif temp[i][0] < m[mid][0] and temp[j][0] < m[mid][0]:
                        continue  # 후보 좌표 i와 j의 x좌표가 모두 중간 좌표값보다 작을 경우 위에서 구한 divideandconquer(m[:mid])에 포함되므로 pass
                    elif temp[i][0] >= m[mid][0] and temp[j][0] >= m[mid][0]:
                        continue  # 후보 좌표 i와 j의 x좌표가 모두 중간 좌표값보다 클 경우 위에서 구한 divideandconquer(m[mid:])에 포함되므로 pass
                    minimumd = min(minimumd, distance(temp[i], temp[j]))
        return minimumd


if n != len(points):
    print(0)
else:
    print(divideandconquer(points))

더 생각해 볼 것?

Python으로 시간 초과로 풀지 못해 PyPy3으로 풀었다. Python으로 풀 수 있을 만큼 더욱 최적화 할 수 있는 방법이 있는지 공부가 필요하다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!