[백준] 2261번 가장 가까운 두점 Java

문제 링크

https://www.acmicpc.net/problem/2261

문제

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

입력

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

출력

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

알고리즘: 분할 정복

풀이

이 문제는 단순하게 O(n제곱)으로 풀면 시간제한을 지킬 수 없다.
병합 정렬 방식으로 푸는 게 이 문제의 핵심이다. -> O(nlog2n)

1. 먼저 점들을 x좌표 기준으로 오름차순 정렬한다.

2. 각 영역의 점의 개수가 3개보다 작아질 때까지 이등분해준다. (분할) O(log2n)

3. 각 영역에서 가장 짧은 길이의 선을 구한다.

4. 병합 과정에서 l_min_dist (왼쪽에서 가장 짧은 선), r_min_dist, min_dist(가장 짧은 선)을 비교해서 min_dist를 업데이트해 준다.

5. 여기서 왼쪽의 점들과 오른쪽의 점들 또한 연결해서 비교해줘야 하는데, 전부 비교하면 n제곱이므로 가능성 있는 좌표들만 추려내서 posi_cord 리스트에 넣어줘야 한다.
   가능성 있는 좌표는 왼쪽과 오른쪽으로 나눈 x좌표를 기준으로 왼쪽으로 min_dist, 오른쪽으로 min_dist만큼의 x좌표들이다.

6. posi_cord에도 무수히 많은 점이 존재할 가능성이 있다. 그래서 이번엔 y좌표를 기준으로 추려내야 한다. 임의의 점에서 위로 min_dist만큼 아래로 min_dist만큼의 점들만 비교해준다.
   그러한 점들 또한 많다고 생각할 수 있는데, 최대 6개 밖에 존재하지 않는다. 다음 그림을 보자

오른쪽 영역에 점들은 min_dist를 변으로 한 정사각형 안에 두 개 이상 들어갈 수 없다. 그 이유는 min_dist보다 짧은 선은 오른쪽 영역에서 존재하지 않기 때문이다. (존재하면 모순임)
그래서 최대로 점의 개수를 찍어보면 총 6개가 나온다. (병합) O(n)

7. 이제 추려낸 점들을 이은 선과 min_dist를 비교해서 업데이트해 주면 된다. 중복을 방지하기 위해서 posi_cord를 y좌표 기준으로 오름차순 정렬해준다. 현재 점의 y좌표 보다 크거나 같은 좌표들만 체크해 주면서 min_dist를 업데이트해 준다.

소스 코드

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

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

public class Main {
    static int N;
    static ArrayList<Coordinate> coordinate = new ArrayList<>();
    static int min_dist = Integer.MAX_VALUE;
    public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      for(int i=0; i<N; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          coordinate.add(new Coordinate(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
      }
      Collections.sort(coordinate, (a,b) -> a.x - b.x);
      find_closesPair(0, coordinate.size() - 1);
      System.out.println(min_dist);
    }
    
    static int cal_dist(Coordinate a, Coordinate b) {
        return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
    }
    
    static void find_closesPair(int s, int e) {
        if(e - s + 1 <= 3) {
            //점이 3개 이하라면 그 중 짧은 선을 찾는다.
            for(int i=s; i<=e; i++) {
                for(int j= i+1; j<=e; j++) {
                    min_dist = Math.min(min_dist, cal_dist(coordinate.get(i), coordinate.get(j)));
                }
            }
            return;
        }
        //분할
        int mid = (s + e) / 2;
        find_closesPair(s, mid);
        find_closesPair(mid+1, e);
        
        //병합
        ArrayList<Coordinate> posi_cord =  new ArrayList<>();
        for(int i=s; i<=e; i++) {
            int xd = (coordinate.get(mid).x - coordinate.get(i).x) * (coordinate.get(mid).x - coordinate.get(i).x);
            if(xd < min_dist) posi_cord.add(coordinate.get(i));
        }
        
        //가능성있는 좌표들을 y좌표 기준으로 오름차순 정렬.
        Collections.sort(posi_cord, (a,b) -> a.y - b.y);
        
        //현재 y좌표에서 y좌표가 같거나 큰 좌표들을 check한다. 중복을 피하기 위해서
        for(int i=0; i<posi_cord.size()-1; i++) {
            for(int j=i+1; j<posi_cord.size(); j++) {
                int yd = (posi_cord.get(i).y - posi_cord.get(j).y) * (posi_cord.get(i).y - posi_cord.get(j).y);
                
                //yd값이 min_dist보다 크거나 같으면 break; 이후 값은 min_dist보다 무조건 큼
                if(yd >= min_dist) break;
                
                //yd값이 min_dist보다 작다면 두 점의 거리를 구해서 min_dist와 비교
                min_dist = Math.min(min_dist, cal_dist(posi_cord.get(i), posi_cord.get(j)));
            }
        }
    }
}