[Judge] 평면좌표계에서 가장 가까운 좌표쌍 찾기

🎯 알고리즘 과제 - 평면좌표계에서 가장 가까운 좌표쌍 찾기

---

🤔 나의 풀이

📌 문제

- 알고리즘 과제 > 평면좌표계에서 가장 가까운 좌표쌍 찾기

📌 날짜

2020.04.15

📌 시도 횟수

Failed

💡 Code

# solution 실행 부분
def solution(pair):
    # 예외 처리
    if len(pair) < 2:
        return format(0, ".2f")
	
    # x에 대하여 정렬된 좌표, y에 대하여 정렬된 좌표 쌍을 각각 px, py라고 한다.
    px = sorted(pair)
    py = sorted(pair, key=lambda x: x[1])
    answer = closest_pair(px, py) # answer : 가장 가까운 좌표 쌍 사이의 거리
    return format(answer, ".2f")


# x축을 기준으로 우선 최소 거리를 구한다.
def closest_pair(px, py):	
	# 좌표쌍이 3개 이하라면 브루트 포스로 최소 거리를 구한다.
    if len(px) <= 3:
        return brute_force(px)

    mid = len(px) // 2
    pxL = px[:mid]	# px의 Left
    pyL = [p for p in py if p[0] < px[mid][0]]	# py의 Left
    pxR = px[mid:]	# px의 Right
    pyR = [p for p in py if p[0] >= px[mid][0]]	# py의 Right
	
    # 비교하고자 하는 좌표쌍이 3개 이하가 될 때까지 분할 정복
    # (왼쪽 분할의 최소 거리, 오른쪽 분할의 최소 거리) 중 더 작은 값이 delta이다.
    delta = min(closest_pair(pxL, pyL), closest_pair(pxR, pyR))
    return closest_split_pair(px, py, delta) # 이번에는 y축을 기준으로 최소 거리를 구한다.


# y축을 기준으로 정렬한 좌표쌍에 대하여 delta보다 작은 거리를 가진 좌표쌍이 있는지 확인한다.
def closest_split_pair(px, py, delta):	
    mid = len(px) // 2
    median_X = px[mid][0]

    # 중심축으로부터 delta 이상 떨어져 있는 좌표는 제외한다.
    candidates = []
    for p in py:
        if abs(p[0] - median_X) < delta: 
            candidates.append(p)

    # 후보자 비교(최대 7번 검사할 수 있음)
    for i in range(len(candidates) - 1):
        for j in range(i + 1, min(i + 8, len(candidates))):
            dist = get_distance(candidates[i], candidates[j])
            delta = min(delta, dist)
    return delta


# 두 좌표 사이의 거리를 리턴
def get_distance(p1, p2):
    x1, y1 = p1[0], p1[1]
    x2, y2 = p2[0], p2[1]
    return math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))


# px(좌표 리스트)를 브루트 포스로 모두 조사하여 최소 거리를 리턴
def brute_force(px):
    min_dist = float("inf")
    for i in range(len(px) - 1):
        for j in range(i + 1, len(px)):
            min_dist = min(min_dist, get_distance(px[i], px[j]))
    return min_dist


# 입력 및 실행
for _ in range(int(input())):
    pair_num = int(input())
    arr = list(map(int, input().split()))
    pairs = []
    for i in range(0, len(arr), 2):
        py = arr[i]
        px = arr[i + 1]
        pairs.append([px, py])
    print(solution(pairs))

💡 문제 해결 방법

1. 정렬된 x에 대하여 왼/오른쪽 부분에서 최소 거리를 각각 찾는다.
2. 해당 왼/오른쪽의 범위 안에 있는 좌표들을 y를 기준으로 정렬한 후
3. delta = (왼쪽 최소 거리, 오른쪽 최소 거리 중 더 작은 값) 라고 했을 때, 중심축으로부터의 거리가 delta 값보다 작은 값들 중..
   현재 좌표로부터 최대 7개를 비교하여 최소 거리를 조사한다.
4. 이렇게 구한 최소 거리를 delta로 갱신하고 다시 1의 결과로 리턴 후 반복...
5. 따라서 이러한 과정(1 ~ 4)의 반복을 통해 최종적으로 가장 가까운 좌표쌍의 거리(delta)를 구할 수 있다.

💡 새롭게 알게 된 점

- 어렵당ㅠ

---