백준 2261 가장 가까운 두 점 Java

정답률 15퍼센트의 가장 가까운 두 점 문제이다.

정답률에서도 알 수 있듯이 굉장히 어려운 문제인 것 같다..

n의 최댓값이 100000, 십만으로 O(n^2)으로 비교하는 간단한 알고리즘으로는 절대 풀 수 없다.

당연히 나도 풀 수 없었고, 백준님의 강의를 토대로

'분할 정복'으로 푼 가장 가까운 두 점 문제를 정리하려고 한다.

 

푸는 방법은 이렇다.

x좌표 순으로 정렬을 한다.

백준님의 강의자료 중에서..

그리고 중간 인덱스를 기준으로 

왼쪽에서 가장 가까운 두점 사이의 거리를 찾고

오른쪽에서 가장 가까운 두점 사이의 거리를 찾는다.

왼쪽에서 구한 값과 오른쪽에서 구한 값 중 더 작은 값을 저장한다.

 

중간값을 기준으로 왼쪽, 오른쪽에서 가장 가까운 두점 사이의 거리는 찾았다.

남은 것은 중간값을 지나는 왼쪽 점과 오른쪽 점 사이의 거리를 비교해보면 된다.

 

왼쪽 점과 오른쪽 사이의 점 거리를 비교할 때

왼쪽 점 전부와 오른쪽 점 전부를 비교해 볼 필요는 없다.

가장 가까운 점을 찾는 것이기 때문에

앞에서 구한 왼쪽, 오른쪽에서 가장 가까운 두점 사이의 거리 보다 멀리 떨어진 점들은 볼 필요가 없다.

이렇게 중간 인덱스를 기준으로 앞에서 구한값인 d만큼의 거리 안쪽에 점만 살펴보면 되는데

이 점들은 중간인덱스의 점을 기준으로 최대 6개, 9개이다.

 

x좌표 순으로 정렬을 했기 때문에

x좌표와 중간값의 거리의 제곱이 구한 값인 d보다 작은 점들만 따로 ArrayList에 넣어준다.

x좌표와 중갑값의 거리의 제곱이 d보다 큰 경우엔 정답이 될 수 없다.

 

그리고 그 ArrayList를 다시 y좌표 순으로 정렬해서

점들의 y좌표들 간의 거리의 제곱이 d보다 작은 값들만 거리를 구해서 

서로 비교하며 최솟값을 찾으면 된다.

 

사실 코드를 보면서 이해하는게 훨씬 쉽다.

코드가 긴편이지만 두 세번만 읽어보면 뭐하는 코드인지는 알 수 있다..

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;
 
public class Q2261 {
 
    static int dist(Point p1, Point p2) { //두 좌표사이의 거리를 구하는 메소드
        return (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y);
    }
    
    static int bruteForce(List<Point> a, int x, int y) { //완전 탐색으로 가장 가까운 거리 찾기
        int ans = -1;
        for(int i=x; i<=y-1; i++) {
            for(int j=i+1; j<=y; j++) {
                int k = dist(a.get(i), a.get(j));
                if(ans == -1 || ans > k)
                    ans = k;
            }
        }
        return ans;
    }
    
    static int closest(List<Point> a, int x, int y) {
        int n = y-x+1;
        if(n <= 3) { //n이 3이하면 완전탐색으로 x부터 y까지 가장 가까운 두 점 사이의 거리를 찾는다.
            return bruteForce(a, x, y);
        }
        
        int mid = (x+y)/2;
        int left = closest(a, x, mid);
        int right = closest(a, mid+1, y);
        int ans = Math.min(left, right);
        List<Point> b = new ArrayList<>(); //왼쪽과 오른쪽 사이의 점들을 저장할 List
        
        for(int i=x; i<=y; i++) {
            int d = a.get(i).x - a.get(mid).x;
            if(d*d < ans) {
                b.add(a.get(i));
            }
        }
        
        Collections.sort(b, new PointComparator()); //y좌표순으로 정렬
        int m = b.size(); 
        for(int i=0; i<m-1; i++) {
            for(int j=i+1; j<m; j++) {
                int k = b.get(j).y - b.get(i).y;
                if(k*k < ans) {
                    int d = dist(b.get(i), b.get(j));
                    if(d < ans) {
                        ans = d;
                    }
                }
                else { //y좌표 순으로 정렬했기 때문에 앞의 가장 가까운 점이 ans보다 크면 더 볼필요가 없다.
                    break;
                }
            }
        }
        return ans;
    }
    
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        List<Point> a = new ArrayList<>();
        
        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(reader.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            a.add(new Point(x, y));
        }
        Collections.sort(a);
        System.out.println(closest(a, 0, n-1));
    }
 
}
class PointComparator implements Comparator<Point>{ //y좌표 순으로 정렬하기 위한 Comparator
 
    @Override
    public int compare(Point o1, Point o2) {
        return o1.y-o2.y;
    }
    
}
class Point implements Comparable<Point>{
    int x;
    int y;
    
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
 
    @Override
    public int compareTo(Point o) {
        int r = this.x - o.x;
        if(r == 0)
            r = this.y - o.y;
        return r;
    }
}

사실 완벽하게 100% 풀이법을 이해하지는 못했다.

정말 어렵다.

똑같은 문제인 5620번 가장 가까운 두 점 사이의 거리를 풀어보려고 했으나

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

5620번: 가장 가까운 두 점의 거리

n의 최대값이 위의 문제(2261)보다 5배나 더크다. 결과는 역시 시간초과였다.

분할정복만으로 푸는 것보다 라인스윕으로 푸는 것이 더 간단할 수도 있으므로

라인스윕 알고리즘을 공부해서 5620번 문제를 풀어봐야 겠다.