가장 가까운 두 점 - 2261

aliceshard·2022년 1월 31일
0

1. 개요

원본 문제 링크: https://www.acmicpc.net/problem/2261

분할 정복을 활용해서 많은 수의 점이 주어졌을 때 가장 가까운 두 점의 거리를 측정한다. 가장 가까운 두 점이 무엇인지는 출력할 필요는 없지만, 알고리즘 구조상 출력하는 것도 불가능은 아니다.

2. 코드

def dist_cal(point1, point2):
    x_dist = (point1[0] - point2[0]) ** 2
    y_dist = (point1[1] - point2[1]) ** 2
    return x_dist + y_dist

def solve(start, end):
    global inf, arr
    # print('start:{}, end:{}'.format(start, end))
    if start == end:
        # print('returned: {}'.format(inf))
        return inf
    mid_idx = (end + start) // 2
    min_dist = min(solve(start, mid_idx), solve(mid_idx + 1, end))

    # calculate candidates respect to x_pos
    arr2 = []
    left_idx = right_idx = mid_idx
    lborder_flag = rborder_flag = False

    arr2.append(arr[mid_idx])
    while right_idx != end:
        right_idx += 1
        if (arr[mid_idx][0] - arr[right_idx][0]) ** 2 < min_dist:
            arr2.append(arr[right_idx])
        else:
            break
    while left_idx != start:
        left_idx -= 1
        if (arr[mid_idx][0] - arr[left_idx][0]) ** 2 < min_dist:
            arr2.append(arr[left_idx])
        else:
            break

    # calculate candidates respect to y_pos
    arr2 = sorted(arr2, key=lambda x: x[1])

    for i in range(0, len(arr2)):
        for j in range(i+1, len(arr2)):
            if arr2[i][0] == arr2[j][0] and arr2[i][1] == arr2[j][1]:
                return 0

            if (arr2[i][1] - arr2[j][1]) ** 2 < min_dist:
                min_dist = min(min_dist, dist_cal(arr2[i], arr2[j]))
            else:
                break

    # print('arr2: {}'.format(arr2))
    # print('returned: {}'.format(min_dist))
    return min_dist

def input_routine():
    global arr, inf
    n = int(input())
    # calculate respect to x_pos
    for i in range(0, n):
        temp = list(map(int, input().split()))
        arr.append(temp)
    arr = sorted(arr, key=lambda x: x[0])
    ans = solve(0, len(arr) - 1)
    return ans

inf = 4000000001
arr = []
ans = input_routine()
print(ans)

3. 풀이 메모

이전에 해결했던 가장 큰 직사각형 문제(링크)와 일맥상통하는 문제이다. 좌/우 구역으로 나누어서 국소적인 스케일에서 최대값을 구하고, 상위 구역에서 중간값을 기점으로 값을 비교하며 후보군을 걸러낸다.

후보군을 걸러내는 방법은 x_pos와 y_pos를 따로 비교하는 방법으로, 가장 처음에는 delta(x)가 min_dist보다 작은지 확인하고, y값에 대해서 한번 더 정렬해 2중 루프로 길이를 비교한다.

이 문제는 1중 루프로 해결될 수 없다.

2차원 직교좌표계에서 임의의 무질서한 좌표(벡터)를 표현할 때는 반드시 2개의 basis가 필요하며, 두 basis는 서로 선형 독립이다. 따라서 여러 개의 무질서한(하나의 basis의 스칼라곱으로 표현이 불가능한) 2차원 좌표계의 복수의 벡터에 대해서는 x좌표와 y좌표가 별도로 고려되어야 한다.

다시 말해, 어느 한 점의 x성분과 y성분은 이 둘을 서로 연관짓는 어떠한 규칙성도 없다. 두 개의 점으로 확장하더라도 이 성질은 그대로 유지되어, 두 점이 갖는 각각의 x성분과 y성분도 서로 간의 연관 관계가 없다.

당연한 말을 주절주절 길게 썼지만, 하고 싶은 말은 다음과 같다.

만약 점들이 2차원 좌표 공간의 어느 한 직선에 모두 존재하도록 주어졌다면, 1중 루프만 갖고 가장 가까운 점을 찾을 수 있었겠지만, 문제에서 점은 랜덤하게 주어지니 어느 한 직선에 존재할 것이라는 보장이 없다. 따라서 1중 루프만 갖고 해결하는 것은 불가능하다.

요컨대, 우리는 활용할 수 있는 규칙성이 아무것도 없다. 어쩔 수 없이 가장 원시적인 방법을 택할 수밖에 없다.

프로그래머 입장에서는 두 점을 비교하는 알고리즘을 작성해야 하고, 이 두 점을 선택하는 과정에서 약간의 꾀를 부리고 싶어질 수 있으나, 점들의 배치와 좌표는 규칙성 없게 주어진다는 문제 구조상 이를 허용하지 않는다. 활용할 수 있는 규칙성이 없으니, 임의의 두 점에 대해서 프로그래머가 얻을 수 있는 정보는 거리 말고는 아무것도 없다.

대신 아예 방법이 없는 것은 아니다. 하다 못해 가망이 없는 점들에 대해서는 앞서 언급한대로 x_pos, y_pos를 먼저 측정해 가지치기를 하는 것이 가능하며, 이를 분할 정복과 적절히 조합한다면 멋있지는 않지만 충분한 성능을 내는 알고리즘을 작성할 수 있다.

4. 코멘트

2중 루프 = O(N^2)이며, 이는 PS에서 만큼은 절대적으로 지양해야 한다고 생각하며 강박적으로 코드를 작성했었으나, 적절한 가지치기가 이루어진다면 성능상에서도 속도를 낼 수 있다는 사실을 알 수 있었다.

그나저나 사흘 내내 머리를 쥐어뜯게 했던 문제인데, 이 글을 쓰는 새벽에 갑자기 백준 '단계별로 풀어보기' 리스트에서 빠지는 것을 실시간으로 목격했다. 돌려줘요.

profile
안녕하세요.

0개의 댓글