[백준알고리즘] 2261번: 가장 가까운 두 점 -Python

[백준알고리즘] 2261번: 가장 가까운 두 점 -Python

https://www.acmicpc.net/problem/2261

2261번: 가장 가까운 두 점

진짜 어이없는 문제다. 문제를 푼 코드가 별 차이 없어 보이는데 내 거만 왜 통과를 안 하는지...

코드는 아래 블로그의 코드를 거의 참조해서 겨우 통과했는데... 이전에 통과하지 못한 코드도 별 차이 없는데 안된다.. 게다가 내가 짠 코드는 PyPy에서만 통과를 한다. ㅡㅡ

대체 무슨 차이인지 모르겠다. 아시는 분 계시면 알려주시면 감사하겠습니다.

https://hon6036.github.io/%EB%B6%84%ED%95%A0%20%EC%A0%95%EB%B3%B5/2261/

 

---

문제를 보자마자 당연히 모든 점을 비교하면 안 될 것은 알았다. 거기서 횟수를 줄일 수 있는 방법은 찾아봐서 문제를 풀게 되었다.

 

line sweeping이며 여러 아이디어들이 있었는데, 그중에 사용한 것은 분할 정복 방법이다. 라인 스위핑도 여기서 사용한 개념은 큰 차이가 없는 것 같다.

 

분할 정복을 여기에 사용한다!라고 하면 왼쪽 영역 / 오른쪽 영역 / 두 영역을 걸친 영역 이렇게 세 가지로 쉽게 구분할 수 있을 것이다. 당연히 왼쪽에서의 최소 길이, 오른쪽에서의 최소길이, 두 영역에서 한 좌표씩 뽑은 두 점의 최소길이 중의 최소를 구하면 될 것이다.

 

하지면 이 문제에서 두 영역에서 한 좌표씩 뽑아 최소 길이를 구할 때 그냥 모든 점들의 조합을 생각하게 되면, 처음부터 모든 점의 거리를 구하는 것과 차이가 없다. 그래서 가지치기를 적절하게 해주어야 한다. 거의 모든 사람이 사용한 방법은 최소 거리를 계속해서 기준으로 삼는 것며, 두 번의 가지치기 개념이 들어간다.

 

첫 번째 가지치기 - x좌표

두 영역에 걸친 최소 길이를 구하기 전에 왼쪽 영역과 오른쪽 영역에서의 최소길이를 구했을 것이다. 이 최소길이를 d라고 하자. 이때 왼쪽과 오른쪽을 나눈 가운데의 x좌표를 기준으로 잡고 mid라고 했을 때, mid-d ~ mid+d에 위치한 x좌표만 확인하면 충분히 거리가 d인 좌표들을 모두 포함시킬 수 있다. 물론 d보다 긴 길이들도 포함이 되지만, 모든 영역에 있는 좌표들을 확인할 필요를 줄여주게 된다.

 

두 번째 가지치기 - y좌표

그렇게 영역을 설정한 이후, 이 영역 안의 좌표들의 모든 길이를 비교한다면 여기서도 시간 초과가 발생한다. 따라서 한 번 더 가지치기를 해주어야 한다는 것이다. 그렇기 때문에 각 점을 한 번씩 기준으로 삼고 다른 점들을 비교하되, 두 좌표의 y좌표의 차이가 d이상이라면, 이 두 좌표는 이미 길이가 최소 길이 d보다 길거나 같다는 것을 의미하게 된다.

 

따라서 아래와 같이 코드를 구성하게 된다. 백준님의 코드나 대부분의 사람들의 코드도 비슷한데 왜 내 코드는 안되는지 모르겠다... PyPy에서만 통과하고... 그 전에도 별 차이 없는데 계속 메모리 초과, 시간 초과, 런타임 에러... 등등 난리가 아니었다.

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
 
def dist(a, b):
    return ((b[0] - a[0])**2 + (b[1] - a[1])**2)
 
def divide_and_conquer(start, end):
    length = end - start
    if length == 2:
        return dist(location[start], location[start+1])
    elif length == 3:
        return min(dist(location[start], location[start+1]), dist(location[start], location[start+2]), dist(location[start+1], location[start+2]))
    else: # length > 3
        mid = (start + end)//2
        d = min(divide_and_conquer(start, mid), divide_and_conquer(mid, end))
        
        midX = location[mid][0]
        cmp_list = []
        for i in range(start, end):
            if (location[i][0] - midX)**2 <= d:
                cmp_list.append(location[i])
        
        clist_len = len(cmp_list)
        if clist_len >= 2:
            cmp_list.sort(key&nbsp= lambda x:x[1])
            for i in range(clist_len - 1):
                for j in range(i+1, clist_len):
                    if (cmp_list[i][1] - cmp_list[j][1])**2 > d:
                        break
                    elif cmp_list[i][0] < midX and cmp_list[j][0] < midX:
                        continue
                    elif cmp_list[i][0] >= midX and cmp_list[j][0] >= midX:
                        continue
                    d = min(d, dist(cmp_list[i], cmp_list[j]))
        return d
 
n = int(input())
location = list(set(tuple(map(int, input().split())) for _ in range(n)))
location.sort(key = lambda x: x[0])
if n != len(location):
    print(0)
else:
    print(divide_and_conquer(0, n))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다