원본 문제 링크: https://www.acmicpc.net/problem/2261
분할 정복을 활용해서 많은 수의 점이 주어졌을 때 가장 가까운 두 점의 거리를 측정한다. 가장 가까운 두 점이 무엇인지는 출력할 필요는 없지만, 알고리즘 구조상 출력하는 것도 불가능은 아니다.
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)
이전에 해결했던 가장 큰 직사각형 문제(링크)와 일맥상통하는 문제이다. 좌/우 구역으로 나누어서 국소적인 스케일에서 최대값을 구하고, 상위 구역에서 중간값을 기점으로 값을 비교하며 후보군을 걸러낸다.
후보군을 걸러내는 방법은 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를 먼저 측정해 가지치기를 하는 것이 가능하며, 이를 분할 정복과 적절히 조합한다면 멋있지는 않지만 충분한 성능을 내는 알고리즘을 작성할 수 있다.
2중 루프 = O(N^2)이며, 이는 PS에서 만큼은 절대적으로 지양해야 한다고 생각하며 강박적으로 코드를 작성했었으나, 적절한 가지치기가 이루어진다면 성능상에서도 속도를 낼 수 있다는 사실을 알 수 있었다.
그나저나 사흘 내내 머리를 쥐어뜯게 했던 문제인데, 이 글을 쓰는 새벽에 갑자기 백준 '단계별로 풀어보기' 리스트에서 빠지는 것을 실시간으로 목격했다. 돌려줘요.