[JAVA] BOJ 백준 2261번 - 가장 가까운 두 점

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

2261번: 가장 가까운 두 점

---

2. 내가 푼 방법

다른 분의 풀이를 참고해 푼 문제이다.

 

음.. 내가 이해한대로 간단하게 설명하면, x의 중간 값을 기준으로 x점의 최단 거리를 구하고, x의 최단 거리가 된 적이 있는 좌표의 y점의 최단 거리를 구한다. 이 과정이 x의 중간 값을 기준으로 오른쪽과 왼쪽 집합을 가지면서 재귀한다.

 

따라서 처음에는 List<Tuple>로 저장한 좌표들을 x를 기준으로 오름차순 정렬해주면서 시작한다. 그 후 x 중간 값을 기준으로 오른쪽과 왼쪽 집합에서 최단 거리를 구하는데, 이때 오른쪽과 왼쪽 집합으로 분류될 수 있는 최소 좌표 개수는 3개이므로 base condition을 e - s + 1 <= 3으로 설정해둔다.

public static void solution() {
    Collections.sort(list, (a, b) -> a.x - b.x);

    result = shortest(0, N-1);
}

public static int shortest(int s, int e) {
    if (e - s + 1 <= 3) {
        return bruteforce(s, e);
    }

    int mid = (s + e) / 2;
    int minlen = Math.min(shortest(s, mid), shortest(mid+1, e));

    return shortestBand(s, e, minlen);
}

 

 

이제 각 집합들에서 최단 거리를 구한다.

x의 중간 값(mid)을 기준으로 x점(s ~ e)의 최단 거리를 구하는데, 최단 거리가 업데이트 될 수 있다면 새로운 리스트에 해당 좌표를 저장해둔다. 그 후, 최단 거리가 될 수 있는 좌표들의 y점들끼리의 최단 거리를 구하하기 위해 band를 y를 기준으로 오름차순 정렬해주고 실제 minlen을 업데이트해 준다.

public static int shortestBand(int s, int e, int minlen) {
    List<Tuple> band = new ArrayList<>();

    int mid = (s + e) / 2;

    for (int i = s; i <= e; i++) {
        int len = list.get(mid).x - list.get(i).x;

        if (len * len < minlen) {
            band.add(list.get(i));
        }
    }

    Collections.sort(band, (a, b) -> a.y - b.y);

    for (int i = 0; i < band.size(); i++) {
        for (int j = i+1; j < band.size(); j++) {
            int len = band.get(i).y - band.get(j).y;

            if (len * len < minlen) {
                minlen = Math.min(minlen, getDistance(band.get(i), band.get(j)));
            }
            else break;
        }
    }

    return minlen;
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B2261.java

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

class Main {
    static int N;
    static List<Tuple> list;
    static int result;

    public static void main (String[] args) throws IOException {
        init();
        solution();
        print();
    }

    public static void solution() {
        Collections.sort(list, (a, b) -> a.x - b.x);

        result = shortest(0, N-1);
    }

    public static int shortest(int s, int e) {
        if (e - s + 1 <= 3) {
            return bruteforce(s, e);
        }

        int mid = (s + e) / 2;
        int minlen = Math.min(shortest(s, mid), shortest(mid+1, e));

        return shortestBand(s, e, minlen);
    }

    public static int shortestBand(int s, int e, int minlen) {
        List<Tuple> band = new ArrayList<>();

        int mid = (s + e) / 2;

        for (int i = s; i <= e; i++) {
            int len = list.get(mid).x - list.get(i).x;

            if (len * len < minlen) {
                band.add(list.get(i));
            }
        }

        Collections.sort(band, (a, b) -> a.y - b.y);

        for (int i = 0; i < band.size(); i++) {
            for (int j = i+1; j < band.size(); j++) {
                int len = band.get(i).y - band.get(j).y;

                if (len * len < minlen) {
                    minlen = Math.min(minlen, getDistance(band.get(i), band.get(j)));
                }
                else break;
            }
        }

        return minlen;
    }

    public static int bruteforce(int s, int e) {
        int len = Integer.MAX_VALUE;

        for (int i = s; i <= e; i++) {
            for (int j = i+1; j <= e; j++) {
                len = Math.min(len, getDistance(list.get(i), list.get(j)));
            }
        }

        return len;
    }

    public static int getDistance(Tuple a, Tuple b) {
        return (int) Math.pow(a.x - b.x, 2) + (int) Math.pow(a.y - b.y, 2);
    }

    public static class Tuple {
        int x;
        int y;

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

    public static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        list = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            list.add(new Tuple(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        br.close();
    }
}

---

4. 결과 및 회고

어려운 문제였다. 유사한 문제로 변형돼서 나오면 풀 수 있을까..?

범위를 나누어 계산하는 분할 정복 방식을 기억해서 나중에 다시 풀어보장.