[백준] #2261 가장 가까운 두 점 ( + 나의 좌표와 가장 가까운 좌표 구하기)

 

2261번: 가장 가까운 두 점

 

📌 문제 이해하기

 

백준 문제를 풀기 전, 원래 아래 문제를 풀었었다.

[문제] 나의 좌표값이 주어지고 임의의 개수 만큼의 좌표들이 주어질 때, 가장 가까운 좌표와의 거리를 구해라. 단 주어진 좌표들이 중복되선 안된다.

 

해당 문제를 풀 때에는, 나의 좌표와 비교만 수행하면 됐기 때문에

입력받은 좌표들을 하나씩 비교하면서 연산을 수행(완전탐색)해도 N번의 연산이 수행되기 때문에

O(N)의 복잡도로 때문에 문제가 되지 않았다.

        // 거리를 기록해 둔 배열을 순회하며 가장 짧은 거리를 찾아내서 minDistance에 할당함
        for(int i=1; i<distance.length-1; i++){
            // 만약 최소 거리가 다음 값보다 크다면, 다음 값이 최소 거리가 될 수 있도록
            if(minDistance > distance[i+1]){
                index=i+1;
                minDistance = distance[i+1];
            }
        }

 

 

하지만, 주어진 백준 문제는

1. 모든 점들에 대해서 비교가 수행되어야 함
2. N이 최대 100,000개가 될 수 있음

 

이라는 조건을 가지기 때문에 위의 방식처럼 일반적인 전체 탐색을 수행하게 된다면 

1. 첫번째 좌표 : 두번째 좌표 ~ N번째 좌표 비교
2. 두번째 좌표 : 세번째 좌표 ~ N번째 좌표 비교
...
n-1. N-1번째 좌표 : N-1번째 좌표 ~ N번째 좌표 비교

=> n(n+1)/2 번의 비교 연산 수행

 

O(N^2) 의 복잡도를 가지게 될 것이다. (약 7억번의 비교 연산이 수행될 수 있다고 한다)

 

따라서 완전탐색이 아닌 분할 정복을 통해서

연산 수행 횟수를 줄여야한다!

 

 

✅ 분할 정복에 들어가기 앞서, 간단히 이해해보자

분할 정복이란, 주어진 문제를 특정 값을 기준으로 분할하여 작은 문제로 만들고

이를 재귀적으로 반복하여 각각의 작은 문제들에 대한 답을 통해 전체 문제의 답을 구하는 방식이다.

(이때 분할 정복이 일반 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것)

 

 

1. Divide : 문제를 더 작은 단위의 문제로 나눔

2. Conquer : 각 하위 문제를 재귀적으로 해결, 이때 문제를 더이상 나눌 수 없을 만큼 작아지면 탈출할 수 있도록 조건 설정

3. Combine : 2번 과정을 통해 얻은 답들을 통해 전체 문제의 답을 구함

 

---

 

public class boj2261 {

    // (distance return distance) 두 점 사이의 거리 구하기

    // (bruteForce return minDistance) 남은 점이 3개 이하인 경우 -> 브루드포스(완전탐색) 방식을 통해 가까운 거리 찾기

    // (closest return minDistance) 가장 가까운 좌표 거리 찾기

        // 범위 값에서 중앙 값 구하기

        // 중앙 값을 기준으로, 왼쪽 영역 오른쪽 영역으로 나누기 -> 나눈 영역에 대해 분할 정복 (재귀)
        // 재귀를 통해 각각 왼쪽과 오른쪽 영역에서의 최소 거리를 구함 -> 둘 중 더 작은 값

        // 왼쪽 영역과 오른쪽 영역에 겹친 좌표 중 최소 거리를 가지는 값 찾기
        // -> 중앙 값을 기준으로 +d 만큼의 영역 내에서 탐색

        // 영역 내 값들의 y 좌표를 기준으로 오름차순 정렬

        // y 좌표를 기준으로 정렬된 좌표값들을 차례대로 비교해야하는데, 모두 비교하는 것이 아닌
        // 거리가 d 보다 작은 경우에만 두 좌표 값의 거리를 구해서 비교한다

        // 만약 비교한 거리가 d보다 작다면 최소 거리를 갱신


    // (main) 좌표를 입력받고 x 축을 기준으로 오름차순 정렬하기

}

 

📌 문제 해체하기 & 코드

1.  (main) 좌표를 입력받고, x축을 기준으로 오름차순 정렬하기

먼저, 임의의 n(2 ≤ n ≤ 100,000)을 입력받고 n번 개의 좌표를 입력받는다.

Point 클래스를 이용하면 x값과 y값을 좌표로 point를 만들 수 있다.

 

입력받은 좌표들에 대해서 분할 정복을 위한 중앙 값을 찾기 위해 x축을 기준으로 오름차순 정렬을 수행한다.

(y축을 기준으로 잡아도 상관 없다, 분할 정복을 위한 중간 값 설정을 위해 하나의 축에 대해서만 정렬을 수행하면 됨)

 

오름차순 정렬을 위해 ArrayList에 대해 sort를 수행하는데

값을 Point로 받았기 때문에 Comparator의 comparingInt를 통해 Point p의 x값을 기준으로 정렬할 수 있다.

https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html

// x값을 기준으로 오름차순 정렬
points.sort(Comparator.comparingInt(p -> p.x));

 

 

Comparator에 대한 더 자세한 내용은 아래 글을 통해 이해해보자

https://st-lab.tistory.com/243

자바 [JAVA] - Comparable 과 Comparator의 이해

// (main) 좌표를 입력받고 x값을 기준으로 오름차순 정렬하기
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        // 입력 받은 좌표 값들을 관리할 ArrayList
        ArrayList<Point> points = new ArrayList<>();

        for(int i=0; i<n; i++){
            String[] inputXY = br.readLine().split(" ");
            int x = Integer.parseInt(inputXY[0]);
            int y = Integer.parseInt(inputXY[1]);

            points.add(new Point(x, y));
        }

        // x값을 기준으로 오름차순 정렬
        points.sort(Comparator.comparingInt(p -> p.x));

        // 정렬된 Points 들에 대해 분할 정복 수행
        
    }

 

 

2.  (getDistance) 두 좌표 사이의 거리 구하기

좌표 P1(x1, y1) 와 P2(x2, y2) 가 있을 때, 두 좌표 사이의 거리 d는

이다.

하지만 문제에서 '두 좌표 사이 거리의 제곱 값'을 출력하라고 했기 때문에

별도의 제곱근 연산 수행 없이 거리 값을 구해도 된다.

// (getDistance return distance) 두 점 사이의 거리 구하기
// 제곱 연산 : Math.pow(value, 제곱할 수) return double
// 제곱근 연산 : Math.sqrt(value) return double
    static int getDistance(Point a, Point b){
        return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
    }

제곱 연산을 위한 Math.pow( ) 와 * 연산 중 어떤 것이 더 빠른지 찾아보았는데

Math.pow가 더 무겁다는 사람도 있고, 더 정확한 연산을 수행해준다는 사람도 있지만

결론은 일반적인 연산(제곱, 세제곱 등)에서는 유의미한 차이가 있지 않은 것 같다.

개인적으로는 Math.pow( )가 가독성면에서 더 좋은 것 같다.

 

3. (bruteForce) 분할 후 남은 값이 3개 이하인 경우 수행할 완전탐색

분할 정복은 하나의 문제를 두개 이상으로 나눠서 해결할 수 있으며, 우리는 중앙 값을 기준으로 2개의 문제로 분할하려고 한다

즉 우리는 좌표들에 대해서 나누고 나눠서 두 좌표만이 남을 때까지 쪼개서 두 좌표의 거리를 구할 수 있다.

 

 

그런데 만약에 다음과 같이 2개 / 1개로 나눠진다면?

1개의 좌표에 대해서는 거리를 구할 수가 없다.

 

따라서 남은 좌표가 3개 이하인 경우(2개 또는 3개), 기존에 너무 많은 연산으로 인해 수행하지 못했던 완전 탐색을 사용해주면 된다

// (bruteForce return minDistance) 남은 점이 3개 이하인 경우 -> 브루트포스(완전탐색) 방식을 통해 가까운 거리 찾기
    static int bruteForce(ArrayList<Point> points, int start, int end){
        int minDistance = Integer.MAX_VALUE;
        for (int i=start; i<end; i++) {
            for(int j=i+1; j<=end; j++){
                minDistance = Math.min(getDistance(points.get(i), points.get(j)), minDistance);
            }
        }
        return minDistance;

 

 

4. (closest) 가장 가까운 좌표 거리 찾기

위의 경우처럼 남은 좌표의 개수가 3개라면 완전 탐색,

그 이상이라면 분할 정복을 통해서 가장 가까운 좌표를 찾아야 비교해야 한다.

    // (closest return minDistance) 가장 가까운 좌표 거리 찾기
    public static int closest(int start, int end) {

        // 만약 남은 좌표값이 3개 이하라면 완전탐색으로 최소값을 찾음
        if(end - start + 1 <= 3)
            return bruteForce(start, end);
            
	/* 
        분할 정복 수행
        */
        
        return minDistance;
    }

 

 

~~ 작성중 ~~

 

        // 범위 값에서 중앙 값 구하기
        int mid = (start + end)/2;

        // 가운데 값을 기준으로, 왼쪽 영역 오른쪽 영역으로 나누기 -> 나눈 영역에 대해 분할 정복 (재귀)
        // 재귀를 통해 각각 왼쪽과 오른쪽 영역에서의 최소 거리를 구함 -> 둘 중 더 작은 값이 minDistance
        minDistance = Math.min(closest(start, mid), closest(mid+1, end));

 

 

        // 가운데 값을 기준으로, 왼쪽 영역과 오른쪽 영역에 겹친 좌표 중 최소 거리를 가지는 값 찾기
        // -> 중앙 값을 기준으로 +d 만큼의 영역 내에서 탐색하기 위해 범위에 해당하는 값들을 band 에 넣어줌
        ArrayList<Point> band = new ArrayList<>();
        for(int i=start; i<=end; i++){
            int target = points.get(mid).x - points.get(i).x;
            // minDistance 는 제곱값이 때문에 target 도 제곱해서 값 비교
            if(target * target < minDistance){
                band.add(points.get(i));
            }
        }

 

 

        // band 내 좌표들을 y 좌표 값을 기준으로 오름차순 정렬
        band.sort(Comparator.comparingInt(p -> p.y));

 

 

 

        // y 좌표를 기준으로 정렬된 좌표값들을 차례대로 비교해야하는데, 모두 비교하는 것이 아닌
        // 거리가 d 보다 작은 경우에만 두 좌표 값의 거리를 구해서 비교한다
        for(int i=0; i<band.size()-1; i++){
            for(int j=i+1; j<band.size(); j++){
                int target = band.get(j).y - band.get(i).y;
                // minDistance 는 제곱값이 때문에 target 도 제곱해서 값 비교
                if(target*target < minDistance){
                    // 만약 비교한 거리가 d보다 작다면 최소 거리를 갱신
                    minDistance = Math.min(minDistance, getDistance(band.get(i), band.get(j)));
                } else {
                	// y 좌표값을 기준으로 오름차순 정렬되어있으므로 minDistance 보다 거리가 벌어지면 반복문 종료
                    break;
                }
            }
        }

 

 

 

📌 전체 코드

package BaekJoon;

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;

public class boj2261 {

    public static ArrayList<Point> points = new ArrayList<>();

    // (getDistance return distance) 두 점 사이의 거리 구하기
    static int getDistance(Point a, Point b){
        return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
    }

    // (bruteForce return minDistance) 남은 점이 3개 이하인 경우 -> 브루드포스(완전탐색) 방식을 통해 가까운 거리 찾기
    static int bruteForce(int start, int end){
        int minDistance = Integer.MAX_VALUE;
        for (int i=start; i<end; i++) {
            for(int j=i+1; j<=end; j++){
                minDistance = Math.min(getDistance(points.get(i), points.get(j)), minDistance);
            }
        }
        return minDistance;
    }

    // (closest return minDistance) 가장 가까운 좌표 거리 찾기
    public static int closest(int start, int end) {

        int minDistance = Integer.MAX_VALUE;

        // 범위 값에서 중앙 값 구하기
        int mid = (start + end)/2;

        // 만약 남은 좌표값이 3개 이하라면 완전탐색으로 최소값을 찾음
        if(end - start + 1 <= 3)
            return bruteForce(start, end);

        // 가운데 값을 기준으로, 왼쪽 영역 오른쪽 영역으로 나누기 -> 나눈 영역에 대해 분할 정복 (재귀)
        // 재귀를 통해 각각 왼쪽과 오른쪽 영역에서의 최소 거리를 구함 -> 둘 중 더 작은 값이 minDistance
        minDistance = Math.min(closest(start, mid), closest(mid+1, end));

        // 가운데 값을 기준으로, 왼쪽 영역과 오른쪽 영역에 겹친 좌표 중 최소 거리를 가지는 값 찾기
        // -> 중앙 값을 기준으로 +d 만큼의 영역 내에서 탐색하기 위해 범위에 해당하는 값들을 band 에 넣어줌
        ArrayList<Point> band = new ArrayList<>();
        for(int i=start; i<=end; i++){
            int target = points.get(mid).x - points.get(i).x;
            // minDistance 는 제곱값이 때문에 target 도 제곱해서 값 비교
            if(target * target < minDistance){
                band.add(points.get(i));
            }
        }
        // band 내 좌표들을 y 좌표 값을 기준으로 오름차순 정렬
        band.sort(Comparator.comparingInt(p -> p.y));

        // y 좌표를 기준으로 정렬된 좌표값들을 차례대로 비교해야하는데, 모두 비교하는 것이 아닌
        // 거리가 d 보다 작은 경우에만 두 좌표 값의 거리를 구해서 비교한다
        for(int i=0; i<band.size()-1; i++){
            for(int j=i+1; j<band.size(); j++){
                int target = band.get(j).y - band.get(i).y;
                // minDistance 는 제곱값이 때문에 target 도 제곱해서 값 비교
                if(target*target < minDistance){
                    // 만약 비교한 거리가 d보다 작다면 최소 거리를 갱신
                    minDistance = Math.min(minDistance, getDistance(band.get(i), band.get(j)));
                } else {
                    break; // y 좌표값을 기준으로 오름차순 정렬되어있으므로 minDistance 보다 거리가 벌어지면 반복문 종료
                }
            }
        }
        return minDistance;
    }

    // (main) 좌표를 입력받고 x값을 기준으로 오름차순 정렬하기
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        // 입력 받은 좌표 값들을 관리할 ArrayList
        //ArrayList<Point> points = new ArrayList<>();

        for(int i=0; i<n; i++){
            String[] inputXY = br.readLine().split(" ");
            int x = Integer.parseInt(inputXY[0]);
            int y = Integer.parseInt(inputXY[1]);

            points.add(new Point(x, y));
        }

        // x값을 기준으로 오름차순 정렬
        points.sort(Comparator.comparingInt(p -> p.x));

        // 정렬된 Points 들에 대해 분할 정복 수행
        System.out.println(closest(0, n-1));
    }
}

 

 

📌 참고 자료

https://st-lab.tistory.com/256

[백준] 2261번 : 가장 가까운 두 점 - JAVA [자바]

 

https://steady-coding.tistory.com/215

[BOJ] 백준 2261번 : 가장 가까운 두 점 (JAVA)