백준 2261번 - 가장 가까운 두점

출처 : 2261번: 가장 가까운 두 점 (acmicpc.net)

2261번: 가장 가까운 두 점

---

가장 가까운 두 점 성공분류

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

1 초

256 MB

24030

3993

1996

15.736%

문제

2차원 평면상에 n개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 있다.

출력

첫째 줄에 가장 가까운 두 점의 거리의 제곱을 출력한다.

예제 입력 1 복사

4

0 0

10 10

0 10

10 0

예제 출력 1 복사

100

 

---

[ 문제 설명 ]

 

그림으로 설명하겠습니다.  

이론은 이분을 많이 참고했습니다. ( BOJ 2261:: 가장 가까운 두 점 – 분할 정복 (Closest Pair Problem) – The Casterian )

 

그림 1 - 가장 가까운 점 설명

그림 2 - 가장 가까운 점 설명

그림 3 - 가장 가까운 점 설명

그림 4 - 가장 가까운 점 설명

---

[ 코드 ]

 

def dist(x1, x2):
    return (x1[0] - x2[0]) ** 2 + (x1[1] - x2[1]) ** 2


# 이론 블로그 참고
def solve(coords, N):
    # 점이 두 개일때는 두점 거리만 구하면 됩니다.
    if N == 2:
        return dist(coords[0], coords[1])
    # 점이 세 개일때는 각 두점 사이의 거리를 구해서 최솟값을 구하면 됩니다.
    elif N == 3:
        return min(dist(coords[0], coords[1]), dist(coords[1], coords[2]), dist(coords[0], coords[2]))
    # ?
    line = (coords[N // 2][0] + coords[N // 2 - 1][0]) // 2
    #print()
    #print("idx: ", N // 2)
    #print("코드스:", coords[N // 2][0], coords[N // 2 - 1][0])
    #print("line:", line)
    # x축을 기준으로 짧은 거리 d를 구합니다.
    d = min(solve(coords[:N // 2], N // 2), solve(coords[N // 2:], N // 2))
    #print("d: ", d)
    # x 축 기준을 잊지 말것
    # 유효 거리 d보다 짧거나 같은 것을 제외하고 나머지는 제외시킵니다.
    # 즉, 두점 거리가 d보다 먼 경우는 제외합니다.
    shortCheck = []
    for subset in coords:
        if (line - subset[0]) ** 2 <= d:
            shortCheck.append(subset)

    shortCheck.sort(key=lambda x: x[1])  # y 좌표 정렬
    # print("shortcheck:", shortCheck)

    if (len(shortCheck) == 1):
        return d
    else:
        yCheck = d
        # x축만 고려하면 아직 고려해야할 점의 개수가 많이 남아있어 시간초과가 뜨게 됩니다.
        # 따라서 y축을 고려해주어 y축 기준의 d보다 긴 경우는 전부 제외시켜 주어야 합니다.
        # 세 가지 경우는 필수로 제외합니다.
        for i in range(len(shortCheck) - 1):
            for j in range(i + 1, len(shortCheck)):
                # y축 기준, 기본적으로 최소 길이 d보다 사이 거리가 긴 경우 제외
                if (shortCheck[i][1] - shortCheck[j][1]) ** 2 > d:
                    break

                yCheck = min(yCheck, dist(shortCheck[i], shortCheck[j]))
    return yCheck


N = int(input())
coords = [list(map(int, input().split())) for _ in range(N)]

coordsSet = list(set(map(tuple, coords)))  # set 정렬(집합)

if len(coordsSet) != len(coords):
    print("0")
else:
    coordsSet.sort()
    # print("coordeset:", coordsSet)
    print(solve(coordsSet, N))

# 해둔 print문을 지워가면서 출력을 보면서 흐름을 따라가는 것도 나쁘지 않은 이해 방법입니다.

 

---

후기

 

복습하는 입장임에도 이문제는 조금 까다롭다

정말로 까다로워서 여러 번 생각하게끔 하게 하는 문제였다.