글 작성자: ST_
728x90





 


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

 

2261번: 가장 가까운 두 점

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

www.acmicpc.net

 

 

 

 

 

 

 

 

 




  • 문제

 



 

 

 

이 번 문제는 분할 정복 카테고리의 마지막 문제인만큼 조금 많이 어려운 문제다. 분할 정복 방식 자체는 이전 문제인 히스토그램에서 가장 큰 직사각형과 접근 방식은 유사하나 조금 더 신경써야할 부분들이 존재하므로 같이 알아보도록 하자.

 

 

 

 

 

 

 

 




  • 알고리즘 [접근 방법]

 



 

 

이 번 문제의 경우 일반적인 분할 정복 방식과 스윕 라인 방식 이렇게 두 가지 풀이 방식이 존재한다.

일단, 일반적인 분할정복 접근 방식처럼 풀이하는 방식을 먼저 보여주고 이후 스윕 라인 방식을 설명하도록 하겠다. 그리고 라인스윕 부분만 보지 말고 분할 정복 방식을 먼저 보시길 바란다. 분할 정복에서 풀이되는 개념이 이후 스윕 라인에서도 적용되기 때문에 그렇다.

 

 

 

 

[풀이 1 : 분할 정복]

 

 

이 문제를 풀기 전에 먼저 히스토그램에서 가장 큰 직사각형 문제를 풀어보시길 바란다. 그 중에서도 Stack이 아닌 분할정복 방식으로 풀이한 방법에 초점을 맞춰서 보시길 바란다. 왜냐하면 이 번 문제가 직전 문제에서 필자가 접근한 분할정복 방식이랑 매우 유사하기 때문이다.

 

 

일단 접근 방법부터 알아보도록 하자.

 

문제를 보면 최대 100,000개의 좌표가 주어질 수 있다. 이를 C++같은 경우 pair로 쉽게 표현할 수 있지만 Java는 직접 구현해주어야하기에 x좌표와 y좌표를 표현하기 위한 Point라는 클래스를 하나 생성하도록 하겠다.

 

class Point {

	int x, y;

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

 

 

 

그리고 두 개의 Point에 대해 거리를 반환하는 함수도 같이 만들어주도록 하자.

기본적으로 거리는 다음과 같은 건 알 것이다.

 

 

 

하지만 문제를 잘 보면 결과적으로 두 점의 거리의 제곱을 출력하라고 했기 때문에 루트를 사용할 필요도 없고, 오히려 루트를 사용하게 되면 부동소수점의 경우 '근사치'이기 때문에 자칫 원하는 결과가 안나올 수 있다. 그러니 루트를 빼고 각 x좌표와 y좌표의 차의 제곱을 더해준 값만 사용하도록 하자.

 

// 두 Point의 거리를 반환하는 메소드
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[] 배열로 좌표를 입력받았다고 가정하고 만약 단순히 모든 점들을 비교하고자 한다면, 즉 브루트포스(brute force) 방식으로 접근한다고 한다면 다음과 같을 것이다.

 

// p[] : Point[] p = new Point[N];

// start = 0, end = N - 1
static int brute(int start, int end) {

	int min = Integer.MAX_VALUE;

	for (int i = start; i < end; i++) {
		for (int j = i + 1; j <= end; j++) {

			int tempDist = dist(p[i], p[j]);

			min = Math.min(min, tempDist);
		}
	}
	return min;
}

 

 

위와 같이 i번째 좌표와 j번째 좌표의 각각 x좌표와 y좌표의 차이를 제곱하여 더한 값을 구한 뒤, 최솟값을 갱신해주는 방식으로 풀이할 수 있다.

 

다만, 문제는 최대 입력받는 개수는 100,000개다. 만약 100,000개의 점들에 대해 위와같이 모든 점들을 서로 비교한다면 약 7억번의 비교 작업이 일어난다.

 

시간 복잡도로 따지자면 O(N2) 일 것이다.

 

 

 

그럼 분할 정복으로 접근하려면 어떻게 해야할까?

 

직전 문제인 히스토그램에서 가장 큰 직사각형 문제의 분할정복 방식이랑 같다. 구간 내의 가운데 점을 기준으로 왼쪽과 오른쪽으로 나누어서 풀이하는 것이다.

 

 

 

위와 같은 점들이 있다고 할 때, 중간 점을 기준으로 왼쪽 부분과 오른쪽 부분으로 분할하면서 접근하면 된다.

 

 

이 떄, 주의해야 할 점이 있다.

1. 입력으로 주어지는 좌표는 정렬되어있는 좌표가 아니다.

2. 분할 정복을 할 때, 원소가 1개만 남을 경우 거리를 탐색하지 못한다.

3. 분할한 구간 내의 두 점에 대한 최솟값이 전체에 대한 최솟값이라고 보장할 수는 없다. 

 

 

1번 문제에 대해 먼저 설명하자면 이렇다.

이 전 문제인 히스토그램 문제의 경우 x좌표에 순차적으로 막대의 높이를 입력받는 형식이었다. 즉, x좌표 순서대로 정렬이 되어있다는 의미다. 하지만 이 번 문제는 좌표가 정렬된 형태로 주어지는 것이 아닌 무작위로 주어진다.

 

즉, 우리가 Point[] 배열을 통해 중간 위치(mid)를 얻어낸다고 한들, 해당 index의 좌표가 그래프로 볼 때, 중간 좌표라고 보장할 수 없으며, 해당 좌표에 대한 왼쪽 인덱스(0~mid)와 오른쪽 인덱스(mid + 1 ~ N)의 좌표들이 가운데 좌표를 기준으로 왼쪽 혹은 오른쪽에 있다고 보장할 수 없다.

 

즉, 분할정복으로 풀이하기위해서 우리가 필요한 것은 하나의 축에 대해서 좌표들을 정렬해줄 필요가 있다는 의미다. 우리는 x축으로 보는 것이 좀 더 편하기 때문에 x축을 기준으로 정렬을 해주어야 한다는 것이다.

 

다음 설명 부터는 x축을 기준으로 정렬 해주었다고 가정하에 설명을 하겠다.

 

 

 

2번 문제의 경우는 다음과 같다.

만약 단순히 분할 정복을 한 뒤, 만약 원소가 2개만 남았을 경우 두 좌표의 거리를 측정하여 반환한다고 한다면 이는 잘못된 풀이다. 이 부분을 쉽게 놓칠 수 있는데 위에서 보여준 그래프에 대해서 만약 분할정복으로 쪼개 들어간다면 다음과 같은 상황이 올 것이다.

 

 

위 처럼 3에 대해서 분할정복을 하게 되면 1개만 남는 경우가 발생한다. 이 말은 결국 해당 원소에 대한 거리 측정은 이루어지지 않는다는 것이다. 

이 부분은 어떻게 해결 할 수 있을까?

 

조금만 생각해보면 1로 쪼개지기 위한 조건은 반드시 3일 수 밖에 없다. (입력 N은 2이상이므로 주어지는 크기가 1인 경우는 존재하지 않다.)

그러면 현재 분할 된 구간의 점의 개수가 3이하라면 맨 처음 필자가 설명한 brute force 방식을 적용시키는 것이다. 즉, 분할 된 부분의 점의 개수가 2 또는 3일 때 거리를 측정하도록 하는 것이다.

 

 

 

 

3번 문제를 이제 설명해야하는데, 사실 이 부분이 가장 키 포인트라 3번을 다루기 전에 지금까지 다룬 것을 한 번 코드로 작성해보자. 

 

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의 거리를 반환하는 메소드 (x^2 + y^2)
	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);
	}

    
	/*
	 * main에서 N을 입력 p = new Point[N] 배열을 만들어
	 * 좌표를 입력받은 후 x축으로 정렬하고
	 * closest(0, N - 1); 을 호출했다고 가정
	 */


	// 브루트포스 방식
	private static int brute(int start, int end) {

		int minDist = Integer.MAX_VALUE;

		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) {

		// 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);
		return minDist;
	}

}

 

 

start~end(포함) 원소 개수가 3개 이하가 될 경우 브루트포스를 통해 거리를 반환하도록 하고, 그 외의 경우 두 부분으로 쪼개면서 분할 정복을 해주면 되는 것이다.

일단 end까지 포함한 원소가 3개 이하라는 것을 직관적으로 볼 수 있도록 end - start + 1 < 4 라고 표현했지만, 이 수식을 이해한다면 end - start < 3 이라고 변경하면 된다.

 

 

 

그러면 이제 본격적으로 3번 문제를 보자.

우리가 히스토그램에서 가장 큰 직사각형을 분할 정복으로 풀 때와 마찬가지로 분할하여 구해진 부분이 항상 조건에 만족하는 값이 나온다고 할 수 없다.

 

위 그림 예시로만 보아도 그렇다.

 

우리가 중간을 기준으로 두 부분을 나누어 탐색한다고 한다면 각 부분에서 최소 거리가 반환이 될 것이다.

그리고 구해진 dleft 와 dright 중 작은 값을 반환하게 될 것이다.

 

하지만 위 그래프에서도 보이듯이 두 녹색 거리 모두 최소 거리가 아니다. 잘 보면 파란색 점 사이의 거리가 최소 거리다. 이처럼 중간 피벗에서 왼쪽과 오른쪽 사이에 최소거리가 껴있을 수 있다는 것이다.

 

즉, 중간으로 나뉘어진 점을 기준으로 왼쪽(중간 포함)에 있는 점과 오른쪽에 있는 점들 사이의 거리도 측정해야하는 것이다.

 

 

그러면 어떻게 측정해야할까? 모든 점들을 측정해야하나? 물론 왼쪽의 점들에 대해 오른쪽에 있는 점들을 대응시켜 중간을 가로지르는 모든 선들의 거리를 측정할 수도 있다. 

 

하지만 이는 매우 비효율적인 것이 느껴지지 않는가? 생각해보자. x축에서 가장 왼쪽에 있는 점과 x축에서 가장 오른쪽에 있는 점 사이의 거리를 측정해야 할 이유가 있을까?  

 

그러기 위해 바로 이용하는 것이 바로 특정 구간에 대해서만 측정하는 것이다.

 

 

한 번 다시 생각해보자. 우리는 왼쪽과 오른쪽 두 구간을 나누어 각 구간에서의 두 점 사이의 거리에 대한 최솟값을 얻었다.

그리고 두 값 중에 작은 것이 두 구간을 합친 구간에 대해 가장 작은 거리일 것이다. 단, 두 구간을 가로지르는 점들의 거리는 포함되지 않는다.

 

위 그래프에서는 약간 애매모호하게 보이긴 하지만 일단 dleft와 dright 중 dleft가 더 작다고 가정해보자. (실제로도 더 작은 거리다)

그럼 우리가 두 구간을 가로지르는 점을 구할 때 굳이 dleft의 거리보다 큰 거리를 구할 필요가 있을까? 없다.

 

무슨 말인가 하면 분할 된 index인 mid를 중심으로 dleft보다 멀리 떨어진 점들은 어차피 dleft 보다 긴 거리를 갖게 될 것이기 때문에 굳이 탐색을 해줄 필요가 없다는 것이다.

 

쉽게 그림으로 이해해보자.

 

 

위 이미지처럼 p[mid]의 x값을 기준으로 dleft 만큼의 구간(Band)내의 점들을 추출하는 것이다. 이렇게 추출 된 점들에 대해 거리를 측정해야하는데, 추출 된 원소에 대해 brute force 방식으로 Band 내의 모든 점들에 대해 거리를 측정하는 방식도 있지만, 이 방식보다 더 효율적인 방법이 있다.

 

생각해보자. 우리가 확인하고자 하는 것은 해당 Band 내의 점들 중에서 dleft 거리보다 작은 거리를 갖는 점이 있는지를 확인하는 것이다. 그렇기 때문에 mid를 기준으로 mid - dleft ~ mid + dleft 의 밴드를 형성하여 해당 점들만 추출했다.

 

그럼 y축에서도 생각을 해봐야 한다. 우리가 위 Band 내의 임의의 두 점에 대해서 y축을 기준으로 dleft보다 크거나 같은 원소를 측정할 필요가 있을까? 없다.

쉽게 말해 임의의 한 점을 두고 다른 점들을 비교할 때 y좌표의 차이가 dleft보다 크다면 거리를 측정할 필요가 없는 것이다.

 

위 처럼 만약 해당 Band내의 점에 대해서 y좌표가 작은 점부터 탐색한다면 진한 회색안에 있는 점들만 거리를 측정하면 된다. 만약 측정했을 때 새로운 최소 거리가 나왔다면 갱신을 해주고, 해당 영역 내 탐색이 종료가 되었다면 그 다음으로 y좌표가 작은 점을 기준으로 똑같이 측정해준다.

 

이후의 과정을 쭉 나열하자면 다음과 같다.

 

 

위와 같이 dleft, 혹은 갱신된 새로운 최소 거리를 따라 부분적으로만 점들의 거리를 구하면 된다.

 

그럼 위 과정을 구현하기 위해 필요한 것이있다. 바로 후보군으로 추출할 때,  추출 된 원소들을 y축으로 정렬해야한다는 것이다. 기존의 Point 배열의 경우에는 x축을 기준으로 정렬되었기 때문에 원소들을 추출하여 새로운 리스트에 저장하게 되면 똑같이 x축에 대해 정렬되어있는 것일 뿐 y축에 대해 정렬되어있는게 아니기 때문이다. 즉 쉽게말해 i번째 원소가 i+1 번째 원소보다 y값이 작다고 보장할 수 없다.

 

그러므로 해당 후보군들에 대해 y축에 대해 오름차순으로 정렬해주어야 한다.

 

 

그럼 위 중간 영역의 탐색 과정을 정리해보면 다음과 같다.

 

1. 일단 분할정복을 통해 왼쪽 혹은 오른쪽에서 얻어진 거리 중 최솟값(dist)을 알아야한다.

2. 그 다음 분할 된 위치인 mid를 기준으로 dist 내에 있는 원소들을 추출하여 후보군으로 만든다.

3. 후보 원소들을 y축에 대해 정렬한다.

4. y값이 낮은 원소부터 차례대로 거리를 측정하되, y + dist 범위 내에 있는 점들만 거리를 측정한다.

5. 얻어진 거리가 기존 최소거리보다 작다면 dist를 갱신한다.

 

 

 

자 그럼 한 번 중간 Band 영역에서의 최소 거리를 구하는 함수를 구현해보자. 최대한 이해하기 쉽게 주석을 달아놓도록 하겠다.

 

 

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;
}

// Y좌표를 오름차순으로 정렬하는 Comparator 익명객체
static Comparator<Point> Ycomp = new Comparator<Point>() {
	@Override
	public int compare(Point o1, Point o2) {
		return o1.y - o2.y;
	}
};

 

 

위와 같이 작성해주면 된다.

다만, 주의해야 할 점은 ArrayList를 사용한만큼 Collections.sort을 통해 Y좌표를 오름차순으로 정렬해주어야하기 때문에 Comparator 익명객체를 하나 생성해주었다.

 

물론 Collections.sort(list, (o1, o2) -> {}); 이런식으로 내부에 람다식으로 만들 수 있지만, 그러면 매 번 객체를 생성해주어야 하기 때문에 불필요한 시간을 잡아먹기에.. 일회성이 아닌이상 어지간하면 잘 안쓰는편이다.

 

이를 토대로 이제 출력과 몇 가지 소스만 만들어주면 된다.

이 때 분할 정복 과정 자체는 O(NlogN) 이지만, 각 서브 문제에 대해 Y축 정렬(Tim Sort)이 있기 때문에 마스터 정리를 이용하면 시간복잡도는 다음과 같다.

O(Nlog2N)

 

 

 

 

 

 

[풀이 2 : 개념 보충 및 활용(라인 스위핑)]

 

위 풀이 방식에서는 따로 설명을 안했지만, 여러분이 위 방법을 정확하게 이해하셨다면 분할정복 방식이 아닌 방식으로도 쉽게 확장하여 풀이할 수 있다.

 

우리가 중간을 가로지르는 점들을 구할 때 일정 거리 내에 있는 원소들만 후보로 골라놓고(필터링) 해당 원소들에 대해서만 부분탐색을 했다. 그럼 이 방식을 활용하여 brute force 방식을 개선할 수 있지 않을까?

바로 이러한 아이디어를 적용하는 것이다.

 

이 방식을 적용하기 위해 우리가 알아야 할 자료구조가 있다.

바로 TreeSet 이다.

 

TreeSet 은 중복되는 원소를 허용하지 않으면서 정렬하는 균형 이진 트리인 자료구조다. 앞서 문제를 읽었을 떄, 여러 점이 같은 좌표를 갖을 수 있다고 했으며 우리가 이 문제를 풀 때 활용했던 것이 x좌표 정렬과 y좌표 정렬이었다. 만약 하나의 좌표에 중복되는 점이 여러개 있을 경우 한 번만 탐색하면 되기 때문에 굳이 여러점을 갖고 있을 필요도 없을 뿐더러, 내부 원소를 정렬 된 상태로 유지시켜주기 때문에 활용하기에 안성맞춤인 자료구조다.

 

분할정복에서는 분할 탐색을 하되, 중간을 가로지르는 구간에 대해서만 체크를 해주면 되었기에 ArrayList에 원소를 추출한 원소를 담고 그 원소들을 y좌표에 따른 정렬을 해주었다. 물론 분할정복에서도 middle band 메소드에서 TreeSet을 써서 구현할 수 있으나, TreeSet은 그 자체가 오버헤드가 큰 자료구조라서(내부는 TreeMap으로 구현됨) 오히려 성능이 낮아질 수 있다. (직접 구현하면 훨씬 빠를 것이다.)

 

하지만, 이 번 방식은 선형적으로 앞부터 탐색해나가면서 한 개의 TreeSet만 활용하여 작성할 수 있기 때문에 이 자료구조를 사용하기로 하겠다. 

 

일단, 간단하게 이미지와 함께 설명하겠다.

 

우리가 키 포인트로 잡은 것 중 첫 번째가 바로 x좌표를 기준으로 일정 거리 이하에 있는 점들을 후보군으로 둔 것이다. 그러면 앞의 원소부터 탐색하기 위해서는 우리가 임의의 두 점을 선택하여 거리를 두어야 할 것이다.

그 임의의 두 점을 우리는 첫 번째 원소와 두 번째 원소인 p[0], p[1] 원소를 임의의 점으로 선택하고, 두 점의 거리를 구하도록 하자.

 

p[0], p[1] 원소 선택

 

 

 

 

그리고 우리가 분할정복 풀이에서 했던 것 처럼 x좌표에 대해 거리에 있는 원소들을 후보군으로 넣는 것이다.

 

단, 이 번에는 양쪽을 가로지르는 원소를 구하는 것이 아니기 때문에 한 점을 기준으로 양쪽 범위를 잡을 필요가 없다.

예로들어 기준이 되는 점을 benchIdx라고 할 때, 분할 정복 방식에서 middle band는 [benchIdx - dist : benchIdx + dist] 를 해주었지만, 이 번에는 순차적으로 탐색하기 때문에 [benchIdx - disit : dist] 혹은 [dist : benchIdx + dist] 중 하나만 선택하여 탐색하면 된다.

 

이 때, 우리는 [benchIdx - disit : dist] 방식을 사용 할 것인데, 이유는 기준점을 두고 기준점 이후의 후보들을 탐색하여 원소를 넣고 짧은 거리가 갱신되면, 일부 후보군 원소들을 삭제 했다가 나중에 탐색할 때 다시 넣어야 하는 경우가 발생하기 때문이다.

오히려 미리 기준점 이전의 원소들 중 후보군으로 넣어둔 뒤, 후보군에 못미치는 원소들은 뺴내고, 기준 점을 후보군에 넣으면서 거리가 갱신되면 그만큼 거리에 못미치는 원소들을 후보군으로 제외시키면 되기 때문이다.

 

말로 설명하기에는 어려우니 일단 이미지를 보면서 이해해보도록 하자.

이미 첫 번째 원소(p[0])와 두 번째 원소(p[1])는 거리가 측정되었기 때문에 p[2]부터 시작하여 이전 원소들에 대해서 측정하는 방식으로 할 것이다.

 

 

일단 위 과정을 설명하자면 기준점인 빨간색 점(bench-Point)을 기준으로 x좌표가 minDist 이내 거리에 있는 후보들을 선정한 뒤(밝은 회색 영역), y좌표에 대해 (기준점 ± minDist) 거리 내에 있는 좌표을 뽑아(진한 회색 영역) 기준점과 뽑힌 원소들과의 거리를 측정한 뒤 더 짧은 거리가 있다면 새 거리로 갱신해주는 것이다.

 

그리고 이 과정이 끝나면 기준점이었던 빨간색 점은 후보군이 된다.

 

좀 만 더 이어서 과정을 보도록 하자.

 

위 과정에서는 minDist가 갱신되지 않는다.

 

minDist가 갱신됨
minDist 갱신 안됨

 

 

이런식으로 탐색과정을 거치는 것이다.

 

조금 더 설명을 덧붙이자면 매 번 기준점에 대해 x좌표에 있는 후보군들 중 x좌표와 기준점의 x좌표의 거리가 midDist보다 크다면 해당 후보군을 제외시키고, 그 다음 y좌표에 대해 minDist 보다 적은 후보군들에 대해서 기준점과 거리를 측정한다.

 

이 과정이 끝나면 기준점을 후보군으로 넣고 위 과정을 반복하는 것이다.

 

이러한 방식을 sweep line 알고리즘이라고 하는데, 정의로 보자면 위 과정처럼 가상의 수직선을 두고 정렬 된 이벤트(Point)들이 있는 평면을 쓸어가면서 처리하는 방식 혹은 모델링을 말한다.

 

일단 코드를 보자면 다음과 같다.

 

// Point[] p 배열은 x축으로 정렬되어있다고 가정
		
TreeSet<Point> set = new TreeSet<Point>(Ycomp);	// Ycomp : y축 정렬 Comparator
		
/*
 * 첫 번째 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;

		/*
		 * [밝은 회색 영역 후보군 필터링]
		 * 
		 * 왼쪽 끝점부터 p[i] 이전 원소들에 대하여 midDist보다 
		 * 멀리 떨어진 원소들은 제외한다.
		 */		
		if(xDist * xDist > minDist) {
			set.remove(targetPoint);
			lowestIdx++;
		}
		else {
			break;
		}
	}

	/*
	 * [진한 홰색 영역 필터링]
	 * p[(-100000, 기준점 - root(minDist)) : 100000, 기준점 + root(minDist)] 사이에 있는
	 * 원소들에 대해 subTree를 얻고, 해당 원소들에 대해 기준점과의 거리를 측정한다.
	 */

	int sqrtMinDist = (int)Math.sqrt(minDist) + 1;	// 소수점 버림 방지를 위해 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);

}

 

 

 

 

위와 같은 방식으로 코드를 작성해주면 된다.

 

그리고 왼쪽 끝점이 추가되었는데, 앞서 이미지를 한 번 확인해보자. TreeSet 은 x좌표에 대한 후보군들이 있는데, 매 탐색마다 일정 거리 이상의 원소들은 후보군에서 제외가 된다.

 

minDist는 탐색과정에서 최소한 계속 일정한 값을 갖거나 작아질 수 밖에 없다. 즉, 한 번 제외 된 후보는 적어도 다시 후보가 될 일이 없다는 의미다. 그러면 우리가 후보군에서 제외하기 위한 탐색을 할 때 굳이 매번 0번째 인덱스부터 거리를 측정할 필요가 있는가?

 

즉, 중복적으로 탐색되는 부분을 없애기 위해 후보군에 있는 원소중 가장 작은 x좌표를 가리키는 변수를 두어 부분적으로만 탐색할 수 있도록 하면 된다는 것이다.

 

그리고 subSet에 대해서는 기본적으로 다음과 같다.

 

TreeSet.subSet(시작 값, 끝 값)

 

C++는 upper bound, lower bound를 활용하여 이진 탐색을 통해 시작 점과 끝 점을 얻어낼 수 있지만, 자바에서는 제공하지 않기 때문에 직접 Point 배열에 대해 구현을 해주어야하는데, TreeSet 자체가 이진 균형 트리이기 때문에 굳이 이진 탐색을 구현 할 필요 없이 subSet을 통해 얻어내면 된다. (물론 구체적으로 따지고 들어가면 size메소드에 대해 오버헤드가 걸리기 때문에 직접 구현하는게 빠르긴 할 것이다.)

즉, TreeSet에 저장되어있는 원소 중 시작 값부터 끝값 사이의 트리를 얻을 수 있는 메소드다. 그래서 y축에 대한 원소만 따로 뺴낼 때, 이미 x축에 대한 후보들이 있는 TreeSet에서 (기준점의 y좌표 ± 최소 거리) 원소들을 얻어낸 것이다.

 

해당 메소드에 대한 API는 다음과 같다.

https://docs.oracle.com/javase/8/docs/api/java/util/TreeSet.html#subSet-E-E-

 

TreeSet (Java Platform SE 8 )

 

docs.oracle.com

 

(참고로 subSet에서 x좌표는 -100,000 ~ 100,000 으로 둔 이유는 어차피 TreeSet에 있는 원소들은 이미 x축 기준으로 후보들이 걸러진 상태라 굳이 (기준점의 x좌표 - 최소거리) 를 해줄 필요가 없기 때문이다. 그렇기에 문제에서 절댓값이 100,000 이하로 주어진다고 했으니 해당 좌표로 해준 것이다.)

 

위 과정을 보면 언뜻 O(N2) 처럼 보이나, 트리에 삽입(logN), 삭제(logN), 서브트리(logN) 모두 logN으로 총 N개의 원소에 대해 진행하기 때문에 시간복잡도는 O(NlogN)이다.

 

 

알단 이해하기 쉽도록 subSet을 따로 빼놓았지만 얻어진 subSet도 for-each문을 통해 y가 정렬된 형태로 반환이 가능하니 for-each구문 안에 넣어도 된다.

 

 

 

 

 

 

 

 




  • 2가지 방법을 사용하여 풀이한다.

 



 

이 번 포스팅은 시간이 빡빡하기도 하고, 알고리즘 자체에 초점을 두고자 하기 때문에 입출력 방식은 따로 나누지 않고 풀이 방식에 대해서만 비교 하도록 하겠다.

 

 

1. 분할 정복

2. 스윕 라인

 

 

 

 





  • 풀이





- 방법 1 : [분할 정복]

 

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;
	}


}

 

 

분할 정복을 이용한 가장 기본적인 방법이라 할 수 있겠다. 조금 어려울 수 있어 최대한 주석으로 설명해놓았으니 천천히 읽어보면서 이해하시길 바란다.

 

앞서 말했듯 StringBuilder 가 아니라 System.out.print(arr[i] + " "); 로 하게되면 시간초과가 나므로 주의하자.

StringBuilder 대신 BufferedWriter를 써도 된다.

 

 










- 방법 2 : [Sweep Line]

 

 

 

두 번째 풀이 방식인 Sweep Line 알고리즘 방식이다.

 

 

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);
		
		
	}

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 




  • 성능




 

 

 

채점 번호 : 30383334  -  방법 2 : Sweep Line

채점 번호 : 30383325  -  방법 1 : 분할 정복

 

 

 

 Sweep Line방식이 좀 더 빠른 것 볼 수 있다.

 

 







  • 정리

 



 

이 번 문제의 경우 아마 많이 어려웠을 것이다. 특히 일정 거리 내에 있는 점들만 측정하는 아이디어를 떠올리 쉽지 않고, 이를 활용한 Sweep Line 방식 또한 생소했으리라 본다.

필자도 포스팅하면서 좀 더 이해하기 쉬운 방법이 있을까 여러 방법으로 이리저리 변경해가면서 다양한 코드들을 제출하는데, 디버깅을 제대로 하지 못하고 틀린 경우도 많았다..

아무쪼록 쉽지 않은 문제라 최대한 풀어 쓰긴 했는데, 다들 이해가 되었으면 좋겠지만 분명 이해가 되지 않는 분들도 계실 것이다. 만약 어렵거나 이해가 되지 않은 부분이 있다면 언제든 댓글 남겨주시면 최대한 빠르게 답변드리겠다.

 

 



저작자표시 비영리 변경금지

'JAVA - 백준 [BAEK JOON] > 기타 문제' 카테고리의 다른 글

[백준] 17298번 : 오큰수 - JAVA [자바]  (44) 2021.01.21
[백준] 15236번 : Dominos - JAVA [자바]  (0) 2020.11.01
[백준] 11653번 : 소인수분해 - JAVA [자바]  (3) 2020.10.18
[백준] 1003번 : 피보나치 함수 - JAVA [자바]  (24) 2020.07.22
[백준] 2748번 : 피보나치 수 2 - JAVA [자바]  (6) 2020.07.21

티스토리툴바