[BOJ] 백준 5620번 : 가장 가까운 두 점의 거리 (JAVA)

문제

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

 

 

입력

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

 

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

 

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

 

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

 

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

 

 

출력

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

 

 

풀이

대표적인 Cloeset Pair 문제였습니다.

 

N이 최대 500,000이므로 일반적인 O(N²)로는 풀리지 않는 문제입니다.

 

따라서, 시간 복잡도를 줄이는 풀이를 사용해야 합니다.

 

 

이 문제를 푸는 방법은 분할 정복과 라인 스위핑이 있습니다.

 

분할 정복으로 푸는 방법을 아직 모르시는 분은 아래 링크를 참조하시길 바랍니다.

 

 

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

 

 

이 문제도 분할 정복으로 풀리지만, 저는 좀 더 빠른 시간 복잡도를 가진 라인 스위핑으로 풀어보려고 합니다.

 

먼저, 알고리즘의 중심 로직부터 살펴보겠습니다.

 

 

1. points 배열을 x좌표에 대해 오름차순으로 정렬한다.

 

2. treeSet을 정의한다. (y좌표를 기준으로 오름차순 정렬, y좌표가 같다면 x좌표를 기준으로 오름차순 정렬.)

 

3. points[0] 과 points[1] 사이의 거리를 최단거리라고 가정한다.

 

4. idx = 2부터 새롭게 후보가 될 점들을 set에 넣는다. 만약, 과거에 후보였던 점들이 현재에는 거리가 d보다 크다면 set에서 제거한다.

 

5. 새롭게 추가한 점들과 idx번째 점 사이의 거리를 구하면서 최단거리를 갱신한다.

 

 

ㅎㅎ 어떻게 하시는지 아직 감이 잘 안오시죠?

 

천천히 1번부터 자세하게 보겠습니다.

 

우선, 분할 정복을 풀 때와 마찬가지로 x 좌표를 기준으로 points를 오름차순 정렬합니다.

 

먼저, set은 한 번 탐색한 점은 다시 탐색하지 않도록 하기 위해서 사용하였습니다.

 

또한, treeSet은 정렬이 가능한 set인데, y좌표에 대해서도 거리가 d 이내에 있는 점들만 고려하기 위해서 사용한 것입니다.

 

3번은 말그대로 초기값 d를 설정해 준 것입니다. 이것을 최소의 거리라고 가정한 뒤, idx = 2부터 d를 계속 갱신해 나갈 것입니다.

 

 

4, 5번이 핵심 전략입니다.

 

idx번째 점에 세로선을 긋는다고 생각해 봅시다.

 

그렇다면, 우리가 후보를 뽑는 방법은 아래 사진과 같습니다.

 

 

 

초록색 점을 기준으로 x좌표와 y 좌표 모두 거리 d 이내에 있는 점들을 모두 후보로 선정하는 것입니다.

 

그리고, 그 과정에서 후보가 된 점들을 set에 넣어주는 것입니다. 위의 사진의 경우 set에는 검은색 점 4개가 들어갑니다.

 

마지막으로, 현재 초록색 점과 후보로 뽑힌 점들과의 거리를 구하면서 d보다 작은 거리가 나온다면 d를 그 값으로 갱신하면 됩니다.

 

비교 작업이 끝났다면, set에 초록색 점도 넣어줍니다.

 

 

이제, 라인을 다음으로 옮겨 봅시다.

 

(idx + 1)번째 점에 세로선을 긋게 되면, x좌표에 해당하는 후보를 먼저 선정해야 합니다.

 

그 전에, 현재 후보가 되지 않을 점을 걸러내야 합니다.

 

우리는 idx번째 점에 대해서 set에 검은색 점 4개와 초록색 점 1개가 들어있다고 하였습니다.

 

이제는 (idx + 1)번째로 기준선이 바뀌었기 때문에 (idx + 1)번째 점의 x 좌표와 set의 모든 요소의 x좌표와 거리가 d보다 큰지 검사해야합니다. 만약, d보다 거리가 크다면 그 점을 set에서 지워버리는 것입니다.

 

버릴 후보와 새롭게 들어온 후보를 모두 추린 후, y좌표에 대해서도 d 거리 이내에 있는 점들을 set에 모두 넣어주고, set에 있는 요소와 현재 점 사이의 거리를 구하면서 d를 최소의 값을 갱신합니다.

 

그리고 마지막에 (idx + 1)번째 점을 set에 넣어주고 기준선을 다음으로 넘깁니다.

 

 

이를 끝점이 도달할 때까지 반복하면, 시간 복잡도 O(NlogN) 만으로 해결이 가능하다는 것을 알 수 있습니다.

 

나머지는 구현 문제인데, 아래 소스코드를 확인하여 작성해 보시길 바랍니다.

 

 

소스코드

 

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

 

 

참고 사이트

Line Sweep 알고리즘 :: 마이구미

 

 

 

[BOJ] 백준 5620 가장 가까운 두 점의 거리

 

 

 

가장 가까운 두 점 찾기