[python]백준 5620번 : 가장 가까운 두 점의 거리

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

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	1700	558	294	40.664%

문제

평면상에 n개의 점 (P1, .... , Pn) 이 놓여져있다고 했을 때, 거리가 최소인 두 개의 점을 구하고 그 거리를 알고 싶다.

입력

입력은 첫 번째 줄에 정수로 된 점의 개수 n이 주어진다.

두 번째 줄부터 n+1번째 줄까지 2개의 정수 x,y가 공백을 사이에 두고 주어진다.

i+1번째 줄은 Pi 의 x,y 좌표를 의미하고 n개의 점에 대해서 주어지게 된다.

점의 개수는 2 ≦ n ≦ 500000 , 좌표의 범위는 -10000 ≦ x,y ≦10000로 주어진다.

또한, 모든 점의 좌표는 같은 것이 없이 다른 것으로 한다.

출력

가장 가까운 두 점 사이의 거리의 제곱을 출력하시오.

나의 답

푸는 데에 실패하였다. 관련 알고리즘 더 공부해야함.

알고리즘

1. 완전 탐색 => 시간 초과가 되는 걸 알지만 한 번 구현해보았다.

   import math
   
   num = int(input())
   point_list = list()
   
   for i in range(0,num):
       point_list.append(list(map(int,input().split())))
   
   def distance(points,min):
       if len(points)==1:
           return min
       x = points[0][0]
       y = points[0][1]
       points=points[1:]
       for point in points:
           tmp = pow(x-point[0],2)+pow(y-point[1],2)
           if tmp ==1:
               return 1
           if tmp<min:
               min = tmp
       return distance(points,min)
   
   print(distance(point_list,987654321))

2. 기준 점을 리스트에서 빼고 vector로 계산해볼까

   어차피 시간 복잡도가 같을 것 같음

3. 각각의 점들을 기준으로 한 어떠한 원형 모양 내의 점만 비교대상으로 두면 어떨까?

   그렇다면 원의 지름은 어떻게 구할 것인가?

   x정렬 한 배열에서 해당 점과 다음 인덱스의 점 사이 거리를 지름으로 두자

   sorting부터 O(n^2)이다.

import math

num = int(input())
point_list = list()

for i in range(0,num):
    point_list.append(list(map(int,input().split())))

def xSorting(arr):
    tmp_arr = list()
    tmp_arr.append(arr[0])
    for i in range(1,len(arr)):
        index = i
        for j in range(i-1,-1,-1):
            if tmp_arr[j][0]>arr[i][0]:
                index = j
        tmp_arr.insert(index,arr[i])
    return tmp_arr

def ySorting(arr):
    tmp_arr = list()
    tmp_arr.append(arr[0])
    for i in range(1,len(arr)):
        index = i
        for j in range(i-1,-1,-1):
            if tmp_arr[j][1]>arr[i][1]:
                index = j
        tmp_arr.insert(index,arr[i])
    return tmp_arr

def calMinDist(arr):
    tmp_arr = list()
    for i in range(0,len(arr)-1):
        x_dist = abs(arr[i+1][0]-arr[i][0])
        y_dist = abs(arr[i+1][1]-arr[i][1])
        if x_dist>y_dist:
            tmp_arr.append(x_dist)
        else:
            tmp_arr.append(y_dist)
    return tmp_arr

def makeCandidate(arr,xs):
    tmp_arr = list()
    for i in range(0,len(xs)):
        tmp = list()
        for obj in xs[i+1:]:
            if abs(obj[0]-xs[i][0])<=arr[i]:
                if abs(obj[1]-xs[i][1])<=arr[i]:
                    tmp.append(obj)
            else:
                break
        tmp_arr.append(tmp)
    return tmp_arr

def minResult(candid, xs):
    min = 987654321
    for i in range(0,len(candid)):
        for obj in candid[i]:
            tmp = pow(xs[i][0]-obj[0],2)+pow(xs[i][1]-obj[1],2)
            if tmp<min:
                min = tmp
    return min

x_sort = xSorting(point_list)
y_sort = ySorting(point_list)

min_arr = calMinDist(x_sort)
candid = makeCandidate(min_arr,x_sort)
print(minResult(candid,x_sort))

다른 답

https://dundung.tistory.com/52

이 블로그의 답이 가장 효율적인듯 싶다.

x정렬 후 왼쪽 오른쪽으로 나누어서 계산하고, 그 결과를 최소값으로 이용하여 가운데의 점들을 계산하는 방식.

왜 왼쪽 오른쪽으로 분할할 생각을 못했을까 ;-;..

• 분할정복 알고리즘
• 라인스위핑 알고리즘 (공부하기)

라인 스위핑 알고리즘

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ후..

---

스위핑 알고리즘 : 특정 선이나 공간을 한쪽에서부터 쓸어버리는 식의 알고리즘

한 번만 전체 공간을 스캔하면서 정답을 구하는 형태

---

결국 해당 문제를 x축 정렬 후, 왼쪽에서 오른쪽까지 훑으면서 비교를 하는 식으로 진행

하지만 여기서도 모든 점을 비교하는 것이 아니라 현재 ans 범위 내에 있는 점만 비교

따라해봤지만 시간 초과 나온 코드... 더 공부하자

import math

num = int(input())
point_list = list()

for i in range(0,num):
    point_list.append(list(map(int,input().split())))

def xSorting(arr):
    tmp_arr = list()
    tmp_arr.append(arr[0])
    for i in range(1,len(arr)):
        index = i
        for j in range(i-1,-1,-1):
            if tmp_arr[j][0]>arr[i][0]:
                index = j
        tmp_arr.insert(index,arr[i])
    return tmp_arr

def ySorting(arr):
    tmp_arr = list()
    tmp_arr.append(arr[0])
    for i in range(1,len(arr)):
        index = i
        for j in range(i-1,-1,-1):
            if tmp_arr[j][1]>arr[i][1]:
                index = j
        tmp_arr.insert(index,arr[i])
    return tmp_arr

def calDist(p1,p2):
    dist = pow(p1[0]-p2[0],2)+pow(p1[1]-p2[1],2)
    return dist


def makeCandidate(arr,bound,min):
    tmp_arr = list()
    x = arr[bound][0]
    y = arr[bound][1]
    for i in range(bound-1,-1,-1):
        if abs(x-arr[i][0])<min:
            if abs(y-arr[i][1])<min:
                tmp_arr.append(arr[i])
        else:
            return tmp_arr
    return tmp_arr

def minResult(arr):
    min = 987654321
    for i in range(1,len(arr)):
        candidate = makeCandidate(arr,i,min)
        for obj in candidate:
            dist = calDist(arr[i],obj)
            if dist ==1:
                return 1
            if dist<min:
                min = dist
    return min

x_sort = xSorting(point_list)
print(minResult(x_sort))