[BOJ 2261] 가장 가까운 두 점

문제 내용이 매우 간단 명료하다.

n개의 점들의 좌표가 주어졌을 때, 가장 가까운 두 점 거리의 제곱을 출력하는 문제이다.

우선 시간 제한은 1초. 그리고 점의 개수가 최대 10만개까지 들어온다.

그렇다면 O(N^2) 으로 완전탐색은 일단 불가능으로 O(NlogN) 으로 생각해보자.

logN 이 들어간다면 정렬을 가장 먼저 떠올릴 수 있다.

가장 가까운 두 점을 알기 위해선, 어쨌든 각 점들 사이의 거리를 계산해야 할 것이고, 그것을 효율적으로 하기 위해서 불필요한 계산은 최대한 피해야 할 것이라는 결론이 나온다.

우선 정렬을 떠올렸으므로 각 점들을 y 또는 x 축 기준으로 정렬한다.

정렬한 뒤, 모든 경우의 수가 아닌, 각 정렬된 점들과 인접한 점들은 거리가 상대적으로 가까울 것이므로 인접한 점들끼리만 비교하는 전략을 생각해보자. 대표적으로 분할정복이 있다.

정렬된 축을 기준으로 정 중앙에 있는 인덱스의 점을 기준으로 왼쪽, 오른쪽으로 나눈다.

한쪽의 점이 3개 이하가 될 때 까지 반복한다.

만약, 한쪽의 점이 3개라면 3번의 계산, 2개라면, 1번의 계산으로 각 점 사이의 최소거리를 구할 수 있다.

각 왼쪽, 오른쪽의 최소 거리를 비교해 최소 거리를 다시 구한다.

하지만 아래 그림과 같이 왼쪽에 있는 점과 오른쪽에 있는 점 사이의 거리가 최소거리가 될 가능성이 여전히 존재한다.

그러므로 왼쪽 오른쪽을 나눈 기준 좌표로부터 현재 구한 최소거리만큼 왼쪽으로 -, 오른쪽으로 + 하여 영역을 지정하고, 그 영역안에 있는 점들을 추려낸 뒤 그 점들 끼리만 다시 최소거리를 계산하여 최종적인 최소거리를 구하는 것이다.

이때, 그 영역안에 있는 추려낸 점들을 다른 축을 기준으로 정렬한다. 만약 처음에 y축 기준으로 정렬 했다면, 이번엔 x축 기준으로 정렬, x축이면 y축 기준으로 정렬하여 비교를 하면 현재 최소거리보다 가까운 점들만 비교하여 더 빠르게 계산할 수 있다.

이렇게 분할정복을 하면 최종적인 정답을 O(NlogN) 으로 계산해 낼 수 있다.

정답은 두 점 사이의 거리 제곱이므로, 거리를 구하는 계산에서 제곱근 사용을 하지 않아도 된다.

더 효율적인 방법인 스위핑 기법도 있다. 그 방법은 다음에..

의식의 흐름