백준(Baekjoon) 2261번 : 가장 가까운 두 점 - python 풀이

JISU LIM·2023년 4월 29일

Algorithm Study Records

목록 보기

42/79

❓백준 2261번 : 가장 가까운 두 점

〽️ 문제 요약

2차원 평면상에 n개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하면 되는 문제.

🤨 접근법

가장 단순하게 접근해보자. n개의 점들 중 2개의 점을 골라 거리를 구하는 모든 경우 중 가장 작은 거리를 구하면 될 것이다. 되겠냐? 이 경우 $O(N^2)$ 의 시간복잡도를 가짐을 어렵지 않게 알 수 있을 것이다.

그렇다면 가장 가까운 두 점을 구할 수 있도록 시간 복잡도를 줄이기 위해 어떤 테크닉을 사용할 수 있을까? 이 문제는 closet pair problem이라고 불리는 아주 유명한 문제이다.

기본적으로 분할 정복 방법으로 접근한다. 2차원 평면상에 점들을 x축 기준 median 인덱스를 가진 점을 중심으로 좌우로 나눈다.

좌우로 분할된 부분에 대해서도 각 영역에 두 개의 점이 남을 때 까지 재귀적으로 분할한다.

이제 각 구역 안의 점들에 대해서는 거리를 구할 수 있고, 재귀적으로 호출했으므로 경계 내에 있는 점 들 사이의 거리 중에서는 최솟값을 구할 수 있을 것이다. 경계 안에 점이 하나만 존재한다면 일단 거리를 float(inf)로 처리하여 반환하자. 지금까지의 과정을 코드로 나타내면 아래와 같다.

def split(tmp_points : list[int]) -> int:
    if len(tmp_points) < 2:
        return float('inf')
    elif len(tmp_points) == 2:
        return get_distance(*tmp_points)
    else:
        n = len(tmp_points) // 2
        min_dist = min(split(tmp_points[:n]), split(tmp_points[n:]))

경계 내에 있는 점 들사이의 거리 중 최솟값을 알았다. 이제 문제는 경계 점들과 다른 점들과의 거리이다. 무작정 아무 점이나 골라서 거리를 측정하게 되면 $O(N^2)$ 방법과 다름이 없다.

우리는 분할 과정에서 경개 내 점들의 최소 거리를 알았다. 이를 D라고 할 때 그렇다면 경계에 위치한 점들은 거리가 D이상 차이나는 점들과는 비교하지 않아도 된다. 조금 더 단순하게 x축으로 D 이상, y축으로 D 이상 차이나는 점들은 걸러도 되는 것이다. 먼저 x축으로 D보다 작은 점들을 후보 점으로 포함하자.

        # x축 기준 후보 점 찾기
        target_x = []
        for i in range(len(tmp_points)):
            if (tmp_points[n][0] - tmp_points[i][0]) ** 2 < min_dist:
                target_x.append(tmp_points[i])

가장 왼쪽 경계에 위치한 점을 기준으로 두 개의 점들이 후보로 선택된다. 이제 후보로 선택된 점들 중 y축으로 D보다 작은 점들만을 선택해 거리를 계산하자. 이를 위해선 후보 점들을 담은 자료구조를 y축을 기준으로 정렬해야 할 것이다. 그리고 현재 최소 거리 D와 비교해 D를 업데이트 한다.

각 경계들에 대해서 모두 위 과정을 수행한다면 예시와 같은 경우 아래와 같이 두 번의 추가 연산만을 수행하게 된다.

        # y 축 기준으로 후보 점들 사이의 거리 비교
        t = len(target_x)
        for i in range(t-1):
            for j in range(i+1, t):
                if (target_x[i][1] - target_x[j][1])**2 < min_dist:
                    min_dist = min(min_dist, get_distance(target_x[i], target_x[j]))
                else:
                    break
				return min_dist

이러한 방식으로 계산량을 줄이는 알고리즘을 Closet Pair Problem에 적용할 수 있다. 추가적으로 각 점에서 후보 점들 사이의 거리를 비교하는 횟수는 n개의 점에 대해 7번을 넘지 않음이 증명되어있다. 따라서 정렬( $O(NlogN)$ ) + 최대 7번 비교( $O(N)$ )의 이는 시간 복잡도를 가지므로 $O(N^2)$ 보다 개선된 알고리즘이다.

🔡 코드

import sys
input = sys.stdin.readline

def get_distance(p1 : list[int], p2 : list[int]) -> int:
    return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2

def split(tmp_points : list[int]) -> int:
    if len(tmp_points) < 2:
        return float('inf')
    elif len(tmp_points) == 2:
        return get_distance(*tmp_points)
    else:
        n = len(tmp_points) // 2
        min_dist = min(split(tmp_points[:n]), split(tmp_points[n:]))
        
        # x축 기준 후보 점 찾기
        target_x = []
        for i in range(len(tmp_points)):
            if (tmp_points[n][0] - tmp_points[i][0]) ** 2 < min_dist:
                target_x.append(tmp_points[i])

        # y축 기준 정렬
        target_x.sort(key=lambda x : x[1])

        # y 축 기준으로 후보 점들 사이의 거리 비교
        t = len(target_x)
        for i in range(t-1):
            for j in range(i+1, t):
                if (target_x[i][1] - target_x[j][1])**2 < min_dist:
                    min_dist = min(min_dist, get_distance(target_x[i], target_x[j]))
                else:
                    break
        return min_dist

def main() -> None:
    n = int(input())
    points = sorted([list(map(int, input().rstrip().split())) for _ in range(n)])
    print(split(points))

if __name__ == '__main__':
    main()

📚 고찰

알고리즘 전공과목에서 배웠던 내용을 문제로 만나니 반갑기도 하면서도, 알면서 구현 못한 내가 미웠다.. 좀 더 열심히 들을 걸 그랬나?? 아니 이걸 이론으로 배우고 실습 한 번 한 다음에 3년 이따 구현해보라고 하면 누가 하겠어!! 아니다 더 열심히 하자. 그래도 뭔가 실제로 활용할 수 있을만한 내용의 알고리즘을 복습할 수 있어서 좋은 기회라고 생각한다.