문제
https://www.acmicpc.net/problem/2261
이해
2차원 평면 상의 n개의 점이 주어질 때 가장 가까운 두 점의 거리를 구하여라.
접근
문제는 단순하다. n개의 점을 조합하여 가장 가까운 두 점의 거리를 구하면 된다.
브루트 포스 방법을 생각해보자. n^2만큼 두 점을 뽑아서 최솟값을 찾으면 되겠다. 하지만 본 방법의 시간복잡도는 100,000^2이기 때문에 불가능하다.
브루트 포스 외에는 방법이 없을까? 그렇지 않다.
위와 같은 점들이 존재한다고 가정해보자. 위의 점들은 편의 상 x축을 기준으로 정렬되어 관리한다고 가정하자. 만일 브루트 포스를 이용한다면 0번부터 n번까지 각각 거리를 계산해야 한다.
하지만 우리는 p1, p2 거리를 계산했을 때 이후에 p1, p8 거리를 계산할 필요가 있을까? 없다.
거리 D(p1, p2)를 우리가 계산했다면 p1을 기준으로 p1과 (p1.x + D(p1, p2)) 이상의 x좌표를 가진 점들을 제외해도 되기 때문이다.
무슨 말인지 모르겠다면 다음 그림을 보자.
p1.x + D 이후의 점 p5, p6, p7, p8은 무조건 D보다 클 수밖에 없기 때문에 제외해도 된다. 본 문제는 이러한 아이디어를 기반으로 경우를 소거해야 한다.
첫번째로 필자는 분할정복으로 접근했다. 각 점들을 x축을 기준으로 정렬한 뒤 반으로 나눠 재귀를 통한 분할정복을 수행한다. 분할정복의 기저 조건은 집합에 포함된 점이 3개 이하일 때로 설정했다.
집합에 점이 1개만 남는다면 거리 계산을 할 수 없다. 따라서, 그의 상한인 3개에서 재귀를 멈춰야 한다. 이러한 조건때문에 기저에서의 분할집합은 점이 2개 or 3개가 남는다.
2, 3개 점에서는 단순히 브루트 포스를 활용해 모두 비교하면 된다.
여기까지라면 분할정복으로 좌우 집합으로 나누고 각 집합의 최소거리를 구할 수 있다. 하지만 이게 진짜 최소거리일까? 아니다.
좌우로 나눴을 때 집합 내부에서는 브루트 포스로 점을 비교하지만 집합 사이의 점끼리는 비교할 수 없다.
위에서 검사하지 않은 p4, p6 거리가 최소가 될 수도 있는 것이다.
그렇다면 집합 간의 거리를 위해서 좌우의 모든 점들 조합을 계산해야 하는 것인가? 그렇지 않다. 여기서 위에서 설명한 핵심 아이디어를 사용할 수 있다. 분할정복으로 좌우의 최소 거리를 구할 수 있었다. 그림에서 minLeft가 minRight보다 작다고 가정하고 이를 minDistance라고 하자. 우리는 좌우 집합의 조합으로 가능한 경우를 계산해서 minDistance와 비교하면 된다. 해당되는 경우는 중간 점인 p4에서 시작하면 된다. 위 아이디어와 마찬가지로 p4와 x간의 거리가 minDistance보다 크다면 검사할 필요가 없다. 작은 경우에만 후보에 넣어두자.
후보 리스트에는 좌우를 포함하여 p4와 x거리가 가까운 점들로만 구성된다. 여기서 모든 경우의 수를 탐색하면 될까? 그렇지 않다. 위처럼 우리는 minDistance정보를 가지고 있다. 우리가 이전에는 x간의 거리를 비교했지만 y는 그러지 않았다. 따라서, 후보들을 y축을 기준으로 정렬한 뒤 y간의 거리가 minDistance보다 작다면 이제는 정말 갱신될 가능성이 있다.
직접 점간의 거리를 계산해보자. 만일 minDistance보다 작다면 minDistance를 새로운 값으로 갱신하면 된다.
이를 반복하면 후보 점들을 탐색하는 동안 minDistance는 계속 작아진다. 작아지면 질수록 분기에 따라 검사할 필요가 없는 점들이 생긴다.
코드를 보면서 설명하겠다.
풀이
private static int closestPointsDistance(xy[] points, int p1, int p2) {
int size = p2 - p1 + 1;
int mid = (p1 + p2) / 2;
if (size <= 3) {
return distanceOfPoints(points, size, p1, p2);
}
int d1 = closestPointsDistance(points, p1, mid);
int d2 = closestPointsDistance(points, mid + 1, p2);
int minD = Math.min(d1, d2);
int d3 = middleBand(p1, mid, p2, minD);
return Math.min(d3, minD);
}분할정복의 전체 코드이다. d1은 좌 구간 최소거리, d2는 우 구간 최소거리이다. 두 거리를 구한 뒤 더 작은 값을 minD로 고정하여 마지막 구간 사이 거리를 계산한다. 구간 사이 거리는 이전에 구한 최솟값을 갱신할 여지가 있기 때문에 최솟값 계산으로 마무리한다.
private static int middleBand(int start, int mid, int end, int minD) {
ArrayList<xy> candidates = new ArrayList<>();
for (int i = start; i <= end; i++) {
int xDist = points[i].x - points[mid].x;
if (xDist * xDist < minD) {
candidates.add(points[i]);
}
}
Collections.sort(candidates, YComparator);
for (int i = 0; i < candidates.size() - 1; i++) {
for (int j = i + 1; j < candidates.size(); j++) {
int yDist = candidates.get(i).y - candidates.get(j).y;
if (yDist * yDist < minD) {
minD = Math.min(candidates.get(i).getDistance(candidates.get(j)), minD);
} else {
break;
}
}
}
return minD;
}위에서 언급했듯이 구간 사이를 계산하기 위해 후보리스트를 사용했다. mid를 기준으로 현재 최솟값보다 x간의 거리가 적을 때 후보에 포함된다. 후보들은 이후에 y축 기준으로 정렬한다. y축도 마찬가지로 모든 경우를 비교하면서 minD를 갱신한다. 함수 수행 동안 점점 minDistance는 작아지기 때문에 속도도 점차 개선된다.
요약을 하자면 다음과 같다.
- x기준을 두어 정렬하자.
- 가능한 경우 (좌, 우, 중간)를 모두 구하자.
- 중간의 경우에는 가능한 후보군을 뽑고 최솟값을 갱신하자.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
public class App {
static int N;
static xy[] points;
static StringTokenizer st = null;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
points = new xy[N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
points[i] = new xy(x, y);
}
Arrays.sort(points, xComparator);
System.out.print(closestPointsDistance(points, 0, N - 1));
}
private static int closestPointsDistance(xy[] points, int p1, int p2) {
int size = p2 - p1 + 1;
int mid = (p1 + p2) / 2;
if (size <= 3) {
return distanceOfPoints(points, size, p1, p2);
}
int d1 = closestPointsDistance(points, p1, mid);
int d2 = closestPointsDistance(points, mid + 1, p2);
int minD = Math.min(d1, d2);
int d3 = middleBand(p1, mid, p2, minD);
return Math.min(d3, minD);
}
private static int middleBand(int start, int mid, int end, int minD) {
ArrayList<xy> candidates = new ArrayList<>();
for (int i = start; i <= end; i++) {
int xDist = points[i].x - points[mid].x;
if (xDist * xDist < minD) {
candidates.add(points[i]);
}
}
Collections.sort(candidates, YComparator);
for (int i = 0; i < candidates.size() - 1; i++) {
for (int j = i + 1; j < candidates.size(); j++) {
int yDist = candidates.get(i).y - candidates.get(j).y;
if (yDist * yDist < minD) {
minD = Math.min(candidates.get(i).getDistance(candidates.get(j)), minD);
} else {
break;
}
}
}
return minD;
}
private static int distanceOfPoints(xy[] points, int size, int p1, int p2) {
if (size == 2) {
return points[p1].getDistance(points[p2]);
}
int d1 = points[p1].getDistance(points[p1 + 1]);
int d2 = points[p1].getDistance(points[p2]);
int d3 = points[p1 + 1].getDistance(points[p2]);
return Math.min(d1, Math.min(d2, d3));
}
static class xy {
int x;
int y;
public xy(int x, int y) {
this.x = x;
this.y = y;
}
public int getDistance(xy o) {
int dx = Math.abs(this.x - o.x);
int dy = Math.abs(this.y - o.y);
return dx * dx + dy * dy;
}
}
static Comparator<xy> YComparator = new Comparator<xy>() {
@Override
public int compare(xy o1, xy o2) {
return o1.y - o2.y;
}
};
static Comparator<xy> xComparator = new Comparator<xy>() {
@Override
public int compare(xy o1, xy o2) {
return o1.x - o2.x;
}
};
}결과
중간 처리를 꼼꼼하게 하지 못해 실수가 있었다. 분할정복까지는 이해했지만 mid를 기준으로 경우의 수를 검토하는 것이 이해하기 어려웠다. 가지치기, 백트래킹 기법의 한 종류라고 생각한다. 최솟값을 지속적으로 갱신하는 것이 용이하다.
