[백준 2261] 가장 가까운 두 점 / 자바 / 분할정복 or 라인스위핑

#문제         

레벨: P2
알고리즘: 분할정복, 라인스위핑
풀이시간: 1시간
힌트 참조 유무: 유

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

---

#문제 풀이        

이 문제는 디게 어렵다. 이분의 블로그를 보고 풀이를 이해했다. 이 분의 글을 보기 전에 이것만 기억해라. 

아이디어는 간단하다(라인 스위핑 풀이에 관한). 직사각형을 생각하자. 우린 그 직사각형을 오른쪽으로 밀며 직사각형 안에 있는 점들끼리 비교할 것이다. 그러나 더 좋은 효율을 내기 위해 그 직사각형을 가로 혹은 세로를 점점 줄이면서 탐색하는 것이다. 

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

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

 

 

---

#풀이 코드   

[분할 정복]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Comparator;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
 
public class Main {
 
	private static Point[] p;
	
	private static class Point {	// 좌표 클래스
		int x;
		int y;
 
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
 
	}
 
	// 두 Point의 거리를 반환하는 메소드
	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);
	}
 
	// Y좌표를 오름차순으로 정렬하는 Comparator 익명객체
	private static Comparator<Point> Ycomp = new Comparator<Point>() {
		@Override
		public int compare(Point o1, Point o2) {
			return o1.y - o2.y;
		}
	};
 
	// X좌표를 오름차순으로 정렬하는 Comparator 익명객체
	private static Comparator<Point> Xcomp = new Comparator<Point>() {
		@Override
		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));
 
 
		int N = Integer.parseInt(br.readLine());
 
		p = new Point[N];
 
		StringTokenizer st;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			p[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
 
		Arrays.sort(p, Xcomp);
 
		System.out.println(closest(0, N - 1));
		br.close();
	}
 
	
	// 브루트포스 방식
	private static int brute(int start, int end) {
 
		int minDist = Integer.MAX_VALUE;
 
		for (int i = start; i < end; i++) {
			Point x0 = p[i];
			for (int j = i + 1; j <= end; j++) {
				minDist = Math.min(minDist, dist(x0, p[j]));
			}
		}
		return minDist;
	}
 
	private static int closest(int start, int end) {
 
		// p[start] ~ p[end] 원소가 3개 이하라면 브루트포스로 거리 반환 
		if (end - start + 1 < 4) {
			return brute(start, end);
		}
		
		// 가운데 index를 구한다.
		int mid = (start + end) / 2;
		
		// left는 start ~ mid, right는 mid+1 ~ end로 분할하여 탐색
		int left = closest(start, mid);
		int right = closest(mid + 1, end);
 
		
		// 각 각의 거리 중 최솟값을 구한 뒤 반환
		int minDist = Math.min(left, right);
 
		// 중간 영역의 최소 거리
		int band = middleBand(start, mid, end, minDist);
		return Math.min(minDist, band);	// 둘 중 작은 값을 반환
	}
 
	private static int middleBand(int start, int mid, int end, int minDist) {
		int xDist;
 
		// index 참조가 많으므로 ArrayList를 활용
		ArrayList<Point> list = new ArrayList<Point>();
		
		// 후보군 추출하기
		int midX = p[mid].x;	// mid인덱스의 x좌표값
		for (int i = start; i <= end; i++) {
			xDist = p[i].x - midX;	// x좌표 차이	
			
			/*
			 * midDist는 제곱값이므로, x좌표거리고 제곱으로 계산해준다.
			 * xDist^2 < midDst 라면 후보군으로 리스트에 넣는다.
			 */
			if (xDist * xDist < minDist) {
				list.add(p[i]);
			}
		}
		
		// 후보군들을 y좌표 기준으로 정렬
		Collections.sort(list, Ycomp);
		
		// 후보군들을 순회하면서 y좌표 차이가 midDist내에 있는 원소들만 거리 측정
		int yDist;
		for (int i = 0; i < list.size() - 1; i++) {
			for (int j = i + 1; j < list.size(); j++) {
				
				/*
				 * i번째 점과 j번째 점을 비교하여 y좌표거리를 측정한다.
				 * 측정된 y좌표거리가 minDist보다 작다면
				 * i, j 점의 거리를 측정하여 midDist와 측정한 거리 중
				 * 작은 값으로 갱신한다.  
				 */
				yDist = list.get(i).y - list.get(j).y;
				if (yDist * yDist < minDist) {
					minDist = Math.min(dist(list.get(i), list.get(j)), minDist);
				}
				
				
				/*
				 *  그 외는 y좌표 차이가 midDist보다 크다는 의미로 i번째 원소에 대한
				 *  측정을 멈추고 다음 점으로 넘어간다. 
				 */
				else {
					break;
				}
			}
		}
		return minDist;
	}
 
 
}

 

[라인 스위핑]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.Comparator;
import java.util.TreeSet;
 
public class Main {
 
	private static Point[] p;
	
	private static class Point {	// 좌표 클래스
		int x;
		int y;
 
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
 
	}
 
	// 두 Point의 거리를 반환하는 메소드
	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);
	}
	
	private static Comparator<Point> Xcomp = new Comparator<Point>() {
		@Override
		public int compare(Point o1, Point o2) {
			return o1.x - o2.x;
		}
	};
	
	/*
	 * 분할정복과는 달리 모든 x, y가 같은 경우
	 * 중복 포인트를 없애기 위해 y가 같다면 x값에 대해서도
	 * 비교를 해주도록 해야한다.
	 */
	private static Comparator<Point> Ycomp = new Comparator<Point>() {
		@Override
		public int compare(Point o1, Point o2) {
			if(o1.y == o2.y) {
				return o1.x - o2.x;
			}
			return o1.y - o2.y;
		}
	};
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		int N = Integer.parseInt(br.readLine());
 
		p = new Point[N];
		
		StringTokenizer st;
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			p[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			
		}
		
		// X축에 대해 p배열을 정렬한다.
		Arrays.sort(p, Xcomp);
		
		// x축에 대한 후보군들을 넣을 set이며 해당 후보군들은 y축에 대해 정렬된다. 
		TreeSet<Point> set = new TreeSet<Point>(Ycomp);
		
		/*
		 * 첫 번째 Point와 두 번째 Point를 최소거리라고 가정하고
		 * 시작한다.
		 */
		int minDist = dist(p[0], p[1]);
		
		// 탐색은 p[2]부터 시작하므로 p[0], p[1]을 후보군이라 가정하고 TreeSet에 넣는다.
		set.add(p[0]);
		set.add(p[1]);
		
		int lowestIdx = 0;	// 왼쪽 끝점
		for(int i = 2; i < N; i++) {
			
			Point benchPoint = p[i];
			
			/*
			 * [밝은 회색 영역 후보군 필터링]
			 * 
			 * 왼쪽 끝점부터 p[i] 이전 원소들에 대하여 midDist보다 
			 * 멀리 떨어진 원소들은 제외한다.
			 */
			while(lowestIdx < i) {
				Point targetPoint = p[lowestIdx];
				
				int xDist = benchPoint.x - targetPoint.x;
				
				/*
				 *  x좌표에 대해 minDist보다 크면 후보군에서 제외한다.
				 *  
				 *  한 번 제외된 원소는 다시 후보군이 될 일이 없으므로
				 *  왼쪽 끝점을 한 칸 이동시킨다.
				 */
 
				if(xDist * xDist > minDist) {
					set.remove(targetPoint);
					lowestIdx++;
				}
				
				/*
				 * x축에 대해 정렬된 상태이기 때문에
				 * 처음 만족하는 후보군을 마주치면 이 후의 후보군들은
				 * x축에 대해 모두 만족하므로 break한다.
				 */
				else {
					break;
				}
			}
			
			/*
			 * [진한 회색 영역 후보군 필터링]
			 * 
			 * p[(-100000, 기준점 - root(minDist)) : 100000, 기준점 + root(minDist)] 사이에 있는
			 * 원소들에 대해 subTree를 얻고, 해당 원소들에 대해 기준점과의 거리를 측정한다.
			 */
			int sqrtMinDist = (int)Math.sqrt(minDist) + 1;
			TreeSet<Point> ySub = (TreeSet<Point>) set.subSet(new Point(-100000, benchPoint.y - sqrtMinDist), new Point(100000, benchPoint.y + sqrtMinDist));
			for(Point v : ySub) {
				minDist = Math.min(minDist, dist(benchPoint, v));
			}
			
			set.add(benchPoint);
 
		}
		
		System.out.println(minDist);
		
		
	}
 
}