백준 가장 가까운 두 점

문제

내가 생각했을때 문제에서 원하는부분

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

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

내가 이 문제를 보고 생각해본 부분

Point 클래스 : 2차원 좌표를 저장하며, x,y 값을 갖는다.
dist 메서드 : 두 점 사이 거리의 제곱을 계산한다.
제곱근 없이 제곱된 거리로 다뤄 효율성을 높였다.
closestPair 메서드 : 분할 정복으로 두 점 사이 가장 가까운 거리(제곱)를 재귀적으로 계산한다.
점들을 반으로 나누어 왼쪽과 오른쪽 구간에서 최소 거리를 따로 계산한다.
중간선 기준으로 좌우를 넘나드는 최단거리 후보점들을 추출해 y좌표 오름차순으로 정렬한 뒤, y좌표가 가까운 점 끼리만 거리 비교를 한다.
이렇게 하면 O(n log n)의 효율적인 탐색이 가능한다.
main 메서드 : 입력을 받고 점 배열을 준비 후, 점들을 x 좌표로 정렬한 뒤, closestPair 호출해서 결과 출력한다.

코드로 구현

package baekjoon.baekjoon_33;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

// 백준 2261번 문제
public class Main1347 {
    static int n;
    static Point[] points;
    static Point[] temp; // 정렬용 임시 배열

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

    public static long dist(Point a, Point b) {
        return (long)(a.x - b.x) * (a.x - b.x) + (long)(a.y - b.y) * (a.y - b.y);
    }

    public static long closestPair(int start, int end) {
        if (end - start == 1) {
            return dist(points[start], points[end]);
        }
        if (end - start == 0) return Long.MAX_VALUE;

        int mid = (start + end) / 2;
        long leftDist = closestPair(start, mid);
        long rightDist = closestPair(mid + 1, end);
        long minDist = Math.min(leftDist, rightDist);

        // 중간선의 x값
        int midX = points[mid].x;

        // 중간선과 거리가 minDist 이하인 후보점 추출
        int idx = 0;
        for (int i = start; i <= end; i++) {
            if ((long)(points[i].x - midX) * (points[i].x - midX) < minDist) {
                temp[idx++] = points[i];
            }
        }

        // 후보점들을 y좌표 기준 정렬
        Arrays.sort(temp, 0, idx, Comparator.comparingInt(p -> p.y));

        // y좌표 기준으로 인접 후보 간 거리 비교
        for (int i = 0; i < idx; i++) {
            for (int j = i + 1; j < idx && (long)(temp[j].y - temp[i].y) * (temp[j].y - temp[i].y) < minDist; j++) {
                long d = dist(temp[i], temp[j]);
                if (d < minDist) {
                    minDist = d;
                }
            }
        }
        return minDist;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        points = new Point[n];
        temp = new Point[n];

        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            int x = Integer.parseInt(input[0]);
            int y = Integer.parseInt(input[1]);
            points[i] = new Point(x, y);
        }

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

        long answer = closestPair(0, n - 1);
        System.out.println(answer);
        br.close();
    }
}

마무리

코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.