[Algorithm] 💠백준 2261 가장 가까운 두 점

0. 문제

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

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

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

1. 문제 간단 해석

x, y의 거리를 계산하여 가장 가까운 두 점 사이 거리의 제곱을 출력

2. 아이디어

분할정복
d 보다 작은 x간의 거리를 가진 point를 새로운 배열에 저장
d보다 작은 y간의 거리를 가진 point이면, x,y좌표의 차이를 구함

3. 핵심 풀이

1) 분할정복

int mid = (start + end) / 2;

int d = Math.min(closestPair(arrList, start, mid), closestPair(arrList, mid + 1, end));

2) d 보다 작은 x간의 거리를 가진 point를 새로운 배열에 저장

for (int i = start; i <= end; i++) {
			int t = arrList.get(mid).x - arrList.get(i).x;

			if (t * t < d) {
				band.add(arrList.get(i));
			}
	}

3) d보다 작은 y간의 거리를 가진 point이면, x,y좌표의 차이를 구함

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

				if (t * t < d) 
					d = Math.min(d, dist(band.get(i), band.get(j)));
				else  
					break;
	}

4. 코드

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

public class Divide_2 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int N = Integer.parseInt(br.readLine());
		ArrayList<Point> arrList = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());

			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			arrList.add(new Point(x, y));
		}
		Collections.sort(arrList, (p1, p2) -> p1.x - p2.x); // x좌표 기준으로 오름차순 정렬.

		bw.write(closestPair(arrList, 0, N - 1) + "\n");
		bw.close();
		br.close();
	}

	public static int dist(Point p, Point q) {
		return (p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y);
	}

	static int bruteForce(ArrayList<Point> arrList, int start, int end) {
		int minDist = Integer.MAX_VALUE;
		for (int i = start; i < end; i++) {
			for (int j = i + 1; j <= end; j++) {
				int k = dist(arrList.get(i), arrList.get(j));
				minDist = Math.min(k, minDist);
			}
		}

		return minDist;
	}

	public static int closestPair(ArrayList<Point> arrList, int start, int end) {
		int n = end - start + 1;

		if (n <= 3) {
			return bruteForce(arrList, start, end);
		}

		int mid = (start + end) / 2;

		int d = Math.min(closestPair(arrList, start, mid), closestPair(arrList, mid + 1, end));

		
		ArrayList<Point> band = new ArrayList<>();
		for (int i = start; i <= end; i++) {
			int t = arrList.get(mid).x - arrList.get(i).x;

			if (t * t < d) {
				band.add(arrList.get(i));
			}
		}
		
		Collections.sort(band, (p1, p2) -> p1.y - p2.y);

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

				if (t * t < d) 
					d = Math.min(d, dist(band.get(i), band.get(j)));
				else  
					break;
				
			}
		}

		return d;
	}

	static class Point {
		int x;
		int y;

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

}

5. 결과

성공~