[백준] 2261 : 가장 가까운 두 점 JAVA 풀이

 

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

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

이 포스트를 참고해서 풀었다

 

이전에 풀었던 히스토그램에서 가장 큰 직사각형의 넓이를 구하는 문제와 전체적인 흐름은 비슷하다.

import java.io.*;
import java.util.*;
public class Main {
	
    // Point 객체 배열 선언
	private static Point[] p;
	
    // Point 클래스 생성
	private static class Point{
		int x;
		int y;
		
        // 생성자
		Point(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	
    // Point객체 o1과 o2의 거리를 구하는 함수
	private static int dist(Point o1, Point o2) {
		return (o1.x-o2.x)*(o1.x-o2.x)+(o1.y-o2.y)*(o1.y-o2.y);
	}
	
    // Point 객체의 y값을 비교해서 오름차 정렬
	static Comparator<Point> Ycomp = new Comparator<Point>() {
		public int compare(Point o1, Point o2) {
			return o1.y-o2.y;
		}
	};
	// Point 객체의 x값을 비교해서 오름차 정렬
	static Comparator<Point> Xcomp = new Comparator<Point>() {
		public int compare(Point o1, Point o2) {
			return o1.x - o2.x;
		}
	};
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // n을 입력받음
		int n = Integer.parseInt(br.readLine());
        // n개의 Point 배열 생성
		p = new Point[n];
		StringTokenizer st;
		
        // n개의 점 좌표를 입력받고 배열에 저장
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			p[i] = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
		}
		// Point 배열p를 x값 오름차순으로 정렬
		Arrays.sort(p, Xcomp);
		
        // 가장 가까운 두 점 사이의 거리 출력
		System.out.println(closest(0, n-1));
	}
	
    // 브루트포스 함수 생성
	private static int brute(int start, int end) {
		// 최단거리 초기화
		int minDist = Integer.MAX_VALUE;
		
        // 기존 최단 거리와 p[i], p[j] 사이의 거리 중 최단 거리를 구함
		for(int i=start;i<end;i++) {
			for(int j=i+1;j<=end;j++) {
				minDist = Math.min(minDist, dist(p[i],p[j]));
			}
		}
		return minDist;
	}
	
    // 두 점 사이의 거리 중 가장 가까운 것을 구하는 함수
	private static int closest(int start, int end) {
    	// 점의 개수가 3 이하면 브루트포스로 거리를 구함
		if(end-start<=3) {
			return brute(start,end);
		}
		
        // 분할을 위해 중간값을 구함
		int mid = (start+end)/2;
		
        // 왼쪽, 오른쪽 구간 각각 최단거리를 구함
		int left = closest(start, mid);
		int right = closest(mid+1, end);
		// 그중 더 작은 값을 minDist에 저장
		int minDist = Math.min(left, right);
		
        // 두 구간의 경계선 부근에 최단 거리인 점이 있을 수 있으므로
        // middleBand 함수를 실행
		int band = middleBand(start, mid, end, minDist);
        // 최단 거리를 구해서 반환
		return Math.min(minDist, band);
	}
	
    // 중간 부근에서 최단 거리를 구하는 함수
	static int middleBand(int start, int mid, int end, int minDist) {
    
		int xDist;
		// 중간지점 - 최단거리 ~ 중간지점 + 최단거리에 위치하는 점을 모아둘 어레이리스트 생성
		ArrayList<Point> list = new ArrayList<Point>();
		
        // 중간에 있는 점의 x값을 midX에 저장
		int midX = p[mid].x;
        // 구간 내에 있는 각 점과 midX의 거리를 xDist에 저장
		for(int i=start; i<=end;i++) {
			xDist = p[i].x - midX;
			
            // xDist가 minDist보다 짧다면 = middleBand에 위치하는 점이라면
            // 어레이리스트에 그 Point 객체를 추가
			if(xDist*xDist < minDist) {
				list.add(p[i]);
			}
		}
		
        // middleBand에 속하는 점들이 저장된 list를 y값 오름차순 정렬
		Collections.sort(list, Ycomp);
		
        // list 내에 있는 점들의 y좌표거리를 구함
		int yDist;
		for(int i=0;i<list.size()-1;i++) {
			for(int j=i+1;j<list.size();j++) {
				
				yDist = list.get(i).y-list.get(j).y;
				
                // y좌표거리가 최단거리보다 짧다면 minDist값 갱신
				if(yDist*yDist < minDist) {
					minDist = Math.min(dist(list.get(i),list.get(j)), minDist);
				}
                // y좌표거리가 최단거리보다 크다면 더 비교할 필요가 없음
				else {
					break;
				}
			}
		}
        // 최단거리를 반환
		return minDist;
	}

}