11월 29일 - 가장 가까운 두 점[BOJ/2261]

2차원 평면상에서 주어진 점들 중 가장 가까운 두 점을 찾는 문제이다.
단순히 모든 점 쌍을 비교하면 O(n²) 시간복잡도를 가지므로, 더 효율적인 해결책이 필요하다.
이 문제는 분할 정복 알고리즘을 이용하여 O(n log n) 시간복잡도로 해결할 수 있다.

코드

import java.io.*;
import java.util.*;

public class Main {

    static final int MAX = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력 처리
        int n = Integer.parseInt(br.readLine());
        Point[] points = new Point[n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            points[i] = new Point(x, y);
        }

        // x좌표 기준 정렬
        Arrays.sort(points, Comparator.comparingInt(p -> p.x));

        // 가장 가까운 두 점의 거리 계산
        int result = findClosestDistance(points, 0, n - 1);
        System.out.println(result);
    }

    // 두 점 사이의 거리의 제곱 계산
    static int distance(Point p1, Point p2) {
        int dx = p2.x - p1.x;
        int dy = p2.y - p1.y;
        return dx * dx + dy * dy;
    }

    // 가장 가까운 두 점의 거리 찾기 (분할 정복)
    static int findClosestDistance(Point[] points, int low, int high) {
        if (low == high) {
            return MAX;
        }

        if (low + 1 == high) {
            return distance(points[low], points[high]);
        }

        int mid = (low + high) / 2;
        int leftMin = findClosestDistance(points, low, mid);
        int rightMin = findClosestDistance(points, mid + 1, high);
        int minDistance = Math.min(leftMin, rightMin);

        // 중간 영역에서 기준선과 x값의 차이가 minDistance 이하인 점들을 찾음
        List<Point> strip = new ArrayList<>();
        int midX = points[mid].x;

        for (int i = low; i <= high; i++) {
            int dx = points[i].x - midX;
            if (dx * dx < minDistance) {
                strip.add(points[i]);
            }
        }

        // y좌표 기준 정렬
        strip.sort(Comparator.comparingInt(p -> p.y));

        // 중간 영역에서의 최소 거리 계산
        for (int i = 0; i < strip.size(); i++) {
            for (int j = i + 1; j < strip.size(); j++) {
                int dy = strip.get(j).y - strip.get(i).y;
                if (dy * dy >= minDistance) {
                    break;
                }
                minDistance = Math.min(minDistance, distance(strip.get(i), strip.get(j)));
            }
        }

        return minDistance;
    }

    // 2차원 좌표를 표현하는 클래스
    static class Point {
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

코드 풀이 과정

1. 문제 접근

• 두 점 사이의 거리를 계산하는 단순한 방법은 O(n²) 복잡도를 가지며, 이는 제한 조건인 최대 100,000개의 점에 대해 비효율적이다.
• 분할 정복 방식을 통해 문제를 효율적으로 해결한다:
  • 점들을 x축 기준으로 정렬한다.
  • 전체 점을 좌우로 나누어 최소 거리를 계산한다.
  • 좌우에서 계산한 최소 거리(leftMin, rightMin)와 중간 영역의 최소 거리를 비교한다.

2. 핵심 함수 설명

distance(Point p1, Point p2)

• 두 점 사이의 거리의 제곱을 계산한다.

static int distance(Point p1, Point p2) {
    int dx = p2.x - p1.x;
    int dy = p2.y - p1.y;
    return dx * dx + dy * dy;
}
findClosestDistance(Point[] points, int low, int high)

• 분할 정복 방식으로 가장 가까운 두 점의 거리를 계산한다.
  • 기저 조건: 점의 개수가 1개일 경우 최대값 반환, 2개일 경우 거리 계산.
  • 분할: 좌우로 나누어 각 영역에서의 최소 거리를 계산.
  • 결합: 좌우에서 계산한 거리와 중간 영역에서 계산한 거리 중 최소값을 반환.

int leftMin = findClosestDistance(points, low, mid);
int rightMin = findClosestDistance(points, mid + 1, high);
int minDistance = Math.min(leftMin, rightMin);

중간 영역 처리

• 중간 영역에서 x 좌표 차이가 최소 거리 이하인 점들을 필터링한 뒤, y 좌표 기준으로 정렬하여 계산.
• y 좌표 차이가 최소 거리 이상이면 더 이상 계산하지 않음.

for (int i = 0; i < strip.size(); i++) {
    for (int j = i + 1; j < strip.size(); j++) {
        int dy = strip.get(j).y - strip.get(i).y;
        if (dy * dy >= minDistance) {
            break;
        }
        minDistance = Math.min(minDistance, distance(strip.get(i), strip.get(j)));
    }
}

So...

분할 정복 기법을 활용하여 O(n log n) 시간복잡도로 해결했다. 처음에는 단순 비교 방식으로 접근하려 했으나 시간 초과 문제를 피할 수 없었다. 중간 영역에서 y 좌표를 기준으로 최소 거리를 효율적으로 계산하는 부분이 핵심이었다. 분할 정복 알고리즘을 구현하며 효율적 데이터 처리가 중요한 문제임을 깨달았다.