[백준(Baekjoon)][자바(java)] 2261 : 가장 가까운 두 점 / 분할 정복

 

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

2261번: 가장 가까운 두 점

 

 

1.  완전 탐색  ( Brute-Force )    --> 시간 초과

 

import java.util.Scanner;

public class Main {		// 시간 초과
	
	public static int getDistanceSquared( int x1, int y1, int x2, int y2 ) {
		return (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
	}

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), d_min = Integer.MAX_VALUE;
		int a[][] = new int[n][2];
		for( int i = 0; i < n; i++ ) {
			a[i][0] = sc.nextInt();
			a[i][1] = sc.nextInt();
		}

		for( int i = 0; i < n; i++ ) {
			for( int j = i+1; j < n; j++ ) {
				int d = getDistanceSquared( a[i][0], a[i][1], a[j][0], a[j][1] );
				d_min = d_min > d ? d : d_min;
			}
		}
		
		System.out.println( d_min );
		sc.close();
	}
}

 

 

2.  스위프 라인  ( Sweep Line )

 

( 이 문제 풀면서 처음 접한 알고리즘. 이해하는 데 시간이 꽤 걸렸다. )

import java.util.Arrays;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
	
	static class Point {
		int x;
		int y;
		Point( int x, int y ) {
			this.x = x;
			this.y = y;
		}
	}
	
	public static int getDistancePow( Point p1, Point p2 ) {
		return (p2.x-p1.x)*(p2.x-p1.x) + (p2.y-p1.y)*(p2.y-p1.y);
	}
	
	public static void main(String[] args) {
		
		// 1
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Point[] p = new Point[n];
		for( int i = 0; i < n; i++ )
			p[i] = new Point( sc.nextInt(), sc.nextInt() );
		sc.close();
		
		// 2
		Arrays.sort( p, ( p1, p2 ) -> p1.x - p2.x );  
		
		// 3		// points set - candidates
		TreeSet<Point> ps = new TreeSet<>( (a, b) -> ( (a.y == b.y) ? a.x - b.x : a.y - b.y ) );
		ps.add( p[0] );  
		ps.add( p[1] );
		long d_pow = getDistancePow( p[0], p[1] );
		int start = 0;
		
		// 4
		for( int i = 2; i < n; i++ ) {
			Point p_c = p[i]; 			// current point
			while( start < i ) {
				Point p_s = p[start];	// start point
				int x = p_c.x - p_s.x;
				if( x*x > d_pow ) {
					ps.remove( p_s );
					start++;
				}
				else 
					break;
			}
			int d = (int)Math.sqrt( (double)d_pow ) + 1;
			Point p_lo = new Point( -100000, p_c.y - d );	// lower bound point
			Point p_up = new Point( 100000, p_c.y + d );		// upper bound point
			for( Point p_r : ps.subSet( p_lo, p_up ) ) {		// points within range
				long dis_pow = getDistancePow( p_c, p_r );
				d_pow = Math.min( d_pow, dis_pow );
			}
			ps.add( p_c );
		}
		System.out.println( d_pow );
		
	}
}

https://www.acmicpc.net/blog/view/25

 

 

 1)  입력 값 받음

   (예)
    6 
    0 0
    5 3
    3 2
    10 3
    8 1
    0 4

 -  이 중에서 가장 가까운 거리 제곱( d_pow )을 구할건데, 초기값을 가장 y축에 가까운 두 점 사이의 거리 제곱으로 할 것임 ( 그림상으로 (0,0), (0,4) )

 

 2)  x축 좌표를 기준으로 오름차순 정렬

 

 3)  가장 가까운 두 점이 될 수 있는 후보들을 담을 TreeSet 생성  ( y축 좌표 기준 오름차순. 같으면 x축 좌표 기준 오름차순 )
     0, 1 번째 점들을 TreeSet에 넣음.
     두 점 사이의 거리 제곱( d_pow = d^2 )을 구함 ( 초기화 )  ( d^2 = pow( x1-x2, 2 ) + pow( y1-y2, 2 ) )
    ( TreeSet -- 중복 허용 안 함 ( set 의 성질 ) + 정렬 ( tree 의 성질 ) 

 

 4)  m ( 2 <= m < n ) 번째 점에서 x 좌표가 d'' 거리 내에 있는 점들만 후보로 정하고 후보가 아닌 점들은 TreeSet 에서 지움
     TreeSet 안의 점들 중, y좌표가 m번째 점을 기준으로 +d'', -d'' 인 점들 안에서 가장 가까운 두 점 사이의 거리 제곱( d^2 )을 구함
     m번째 점을 TreeSet에 넣음 ( 후보에 넣음 )   ( d'' = sqrt( d^2 ) + 1 )  ( d = sqrt( d^2 ) )
    ( d => 0 ~ m-1 번째 점들 중 가장 가까운 두 점 사이의 거리 )

가로가 x축, 세로가 y축

 

 

3.  분할 정복  ( Divide and Conquer )

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
	
	static Point p[];
	
	static class Point {
		int x;
		int y;
		Point( int x, int y ) {
			this.x = x;
			this.y = y;
		}
	}
	
	static int getDistancePow( Point p1, Point p2 ) {
		return (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y);
	}
	
    // (4)
	static int bruteForce( int left, int right ) {
		int d_min = Integer.MAX_VALUE;
		for( int i = left; i < right; i++ ) {
			for( int j = i+1; j <= right; j++ ) {
				int d = getDistancePow( p[i], p[j] );
				if( d_min > d ) d_min = d;
			}
		}
		return d_min;
	}
	
    // (3)
	static int divCon( int left, int right ) {
		
        // 4
		int size = right - left + 1;	 // section size
		if( size <= 3 ) 
			return bruteForce( left, right );
		
        // 5
		int mid = ( left + right ) / 2;
		int d_s_left = divCon( left, mid );		// left section distance
		int d_s_right = divCon( mid+1, right );	// right section distance
		
		int d_min = Math.min( d_s_left, d_s_right );
		
        // 6
		List<Point> s_mid = new ArrayList<>();	// middle section
		for( int i = left; i <= right; i++ ) {
			int d_x = p[i].x - p[mid].x;
			if( d_x * d_x < d_min )
				s_mid.add( p[i] );
		}
		
        // 7
		Collections.sort( s_mid, ( p1,p2 ) -> p1.y - p2.y );
		int size = s_mid.size();   // candidate size
		for( int i = 0; i < size-1; i++ ) {
			for( int j = i+1; j < size; j++ ) {
				int d_y = s_mid.get(j).y - s_mid.get(i).y;
				if( d_y * d_y < d_min ) {
					int d = getDistancePow( s_mid.get(i), s_mid.get(j) );
					if( d_min > d ) d_min = d;
				}
				else break;
			}
		}
		return d_min;		
	}
	 
	public static void main(String[] args) {
		
        // 1
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		p = new Point[n];
		for( int i = 0; i < n; i++ )
			p[i] = new Point( sc.nextInt(), sc.nextInt() );
		sc.close();
		
        // 2
		Arrays.sort( p, ( p1,p2 ) -> p1.x - p2.x );
		
        // 3
		System.out.println( divCon( 0, n-1 ) );
	}
}

코드 참고 : https://octorbirth.tistory.com/274

 

 1)  입력 받음  ( Point[0...n-1] )

 2)  x축 좌표 기준으로 오름차순 정렬

 3)  분할정복  ( left = 0, right = n-1 )

 4)  left ~ right 구간이 3 이하인 경우 완전 탐색으로 구함 ( 비교할 점들이 3개 이하인 경우 )

 5)  왼쪽 구간( left ~ mid )에서 d( 가장 가까운 두 점 사이의 거리의 제곱 )를 구함
      오른쪽 구간( mid+1 ~ right )에서 d를 구함
      둘 중 더 작은 d를 구함

 6)  d가 왼쪽 구간과 오른쪽 구간에 걸쳐 있는 경우가 있을 수 있으므로
      left번째부터 right번째까지 mid번째 점과의 x 좌표 거리 제곱이 d 보다 가까운 점들을 List에 넣음

 7)  List를 y축 좌표 기준으로 오름차순 정렬
     루프를 돌며 List 안의 각 점들끼리 y 좌표 거리 제곱이 d 보다 가까운 점을 구해 가장 작은 d를 구함