[BOJ] 백준 2261번 : 가장 가까운 두 점 (JAVA)

문제

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

 

 

입력

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

 

 

출력

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

 

 

풀이

대표적인 Closest Pair 문제였고, 굉장히 난이도 있는 이론입니다.

 

 

(1) 일반적인 방법

N이 10000 미만으로 충분히 작다면, 브루트포스로 O(N²) 만큼의 시간복잡도로 가장 가까운 두 점을 구할 수 있습니다.

 

 

(2) 분할 정복

하지만, 이 문제에서는 N이 100000으로, O(N²)으로는 시간 초과가 발생할 수 밖에 없었습니다.

 

그래서 무턱대고 브루트포스를 사용하면 안 되고, 분할 정복 기법을 이용해야 합니다.

 

일단, 아래와 같이 주어진 점들을 x좌표를 기준으로 오름차순 정렬을 하고, i번째와 (i + 1)번째의 x 좌표 평균을 중앙선으로 잡겠습니다.

 

그렇다면, 문제는 총 3가지로 나뉘게 됩니다.

 

 

1) 가장 가까운 두 점이 왼쪽 영역에 있는 경우

 

2) 가장 가까운 두 점이 오른쪽 영역에 있는 경우

 

3) 가장 가까운 두 점이 왼쪽과 오른쪽 영역 하나씩 있는 경우

 

 

이 때, 1번과 2번은 재귀적으로 쉽게 구할 수 있습니다. 

 

다만, 3번은 왼쪽 영역에서 n/₂개가 있고, 오른쪽 영역에서 n/₂개가 있으므로, 둘을 하나씩 뽑는 경우는 n²/₄가 됩니다.

 

따라서, 3번 문제때문에 시간복잡도는 T(N) = T(N/₂) + O(N²) = O(N²)이 됩니다.

 

 

그렇다면, 어떻게 시간복잡도를 줄일 수 있을까요?

 

우선, 아래처럼 1번과 2번 과정에서 얻을 수 있는 거리인 dl, dr을 구한 뒤, 더 작은 값을 d로 취합시다.

 

 

 

 

제가 취하려는 핵심 전략은 중앙선을 기점으로 d만큼 떨어진 점만 보는 것입니다.

 

 

 

 

위의 사진처럼 중앙선을 기준으로 d만큼 떨어진 지역을 band라고 부릅니다.

 

우리는 이제, 이 band 안에 있는 점에 대해서만 거리를 구해주면 됩니다.

 

 

하지만, 이것으로도 시간 복잡도는 문제는 해결되지 않을 수 있습니다.

 

왜냐하면, 무수한 점이 band에 존재할 수 있기 때문이죠.

 

 

이를 해결하기 위해서는 band에 있는 점들을 y좌표를 기준으로 오름차순 정렬하는 전략을 사용합니다.

 

y좌표를 기준으로 정렬한 뒤, 제일 아래에 있는 점(i₁)부터 시작해서 자기보다 위에 있는 점들끼리만 거리를 비교하는 것이죠.

 

이때, 거리가 d를 초과한다면, 비교하던 대상을 멈추고 시작점을 P_i에서 P_{i + 1}으로 옮겨서 다시 P_{i + 1}보다 위에 있는 점들끼리 거리를 비교하는 작업을 반복하면 됩니다.

 

 

여기서, 우리는 "자기보다 위에 있고, d보다 작은 점이 무수히 많을 수도 있지 않나?"라는 의문이 들 수 있습니다.

 

하지만, 놀랍게도 그 점들은 몇 개 되지 않습니다.

 

우선, 저는 중복을 피하기 위해서 자기보다 큰 점에 대해서 거리를 구한다고 했는데, 그 부분은 잠시 잊어 두고 한 점에 대해서 비교해야하는 최대 점의 개수를 구하겠습니다.

 

 

 

 

어떤 왼쪽 영역에 존재하는 점 p에 대하여 비교해야하는 점의 개수를 구하려면, 오른쪽 영역에 있는 d * 2d 사이즈의 직사각형 안에 있는 점을 보면 됩니다.

 

일단, d * d 사이즈의 정사각형 안에 몇 개의 점이 들어갈 수 있는지 알아봅시다.

 

정사각형 안에 무수한 점이 들어갈 수 있겠다고 생각할 수 있는데, 우리는 오른쪽 영역 각 점들의 거리는 최소 d보다 크거나 같다는 사실을 위에서 구했습니다. (d = min(dl, dr))

 

따라서, 만약, dr이 d와 같다고 가정하면, 정사각형 안에 있는 점의 각 꼭짓점에 해당하는 4개가 됩니다.

 

반대로, dl이 d와 같다고 가정하면, dr은 d보다 크기 때문에, 정사각형 안에 들어있을 수 있는 점의 최대 개수는 3개가 됩니다.

 

같은 이유로 d * 2d는 dr == d일 때는 점이 최대 6개, dl == d일 때는 점이 최대 5개가 된다는 사실을 알 수 있습니다.

 

따라서, 왼쪽이나 오른쪽 영역에 있는 어떤 점 p에 대해서 최대 6개까지의 점만 비교하면 되므로 모든 점에 대하여 자기보다 위에 있는 점을 비교하는 시간은 O(N) 밖에 걸리지 않습니다.

 

 

결과적으로, 3번 문제를 푸는 데 걸리는 시간 복잡도는 O(NlogN)이 되고, 1~3번 문제를 푸는 데 전체 걸리는 시간 복잡도는 T(n) = T(N/₂) + O(NlogN) = O(Nlog²N) 으로 O(N²)에 비해서 줄어들게 됩니다!

 

 

이제, 위 과정을 소스코드로 잘 작성해야하는데, 아래 소스코드를 참고하시길 바랍니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.

 

 

참고 사이트

BOJ 2261:: 가장 가까운 두 점 – 분할 정복 (Closest Pair Problem) – The Casterian

 

 

알고리즘) Closest Pair

 

 

 

Closest Pair of Points using Divide and Conquer algorithm - GeeksforGeeks