Problem

Solution

• 완전 탐색의 시간 복잡도는 O(N2)이다. N≤100,000이므로 완전 탐색으로는 문제를 해결할 수 없다.
• 분할 정복을 이용한다면 문제를 O(NlogN)안에 해결할 수 있다.
• 2차원 평면을 x축 중심선을 기준으로 똑같은 두 평면으로 나눈다. 왼쪽 평면을 A, 오른쪽 평면을 B, 가장 가까운 두 점의 거리를 d라고 할 때, 1)A에서의 d, 2)B에서의 d, 3)A의 한 점과 B의 한 점 사이의 거리의 최솟값을 각각 구해서 3개의 값 중 최솟값을 구하는 알고리즘이다.
• 다만 3) 을 구하는 알고리즘의 시간 복잡도는 O(N2)으로 제한 사항을 추가하지 않으면 시간 초과가 발생한다.
• 두 점의 x값의 차이가 최솟값보다 작은 점들로 하나의 배열을 생성하여 y값에 대해 정렬한 후 y값의 차이가 최솟값보다 크면 반복문을 종료함으로써 3) 을 구하는 알고리즘의 시간 복잡도를 크게 줄일 수 있다. 자세한 사항은 아래의 코드를 참조해주세요.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

const int MAX = 2000000000;

int N;
vector<pair<int, int>> arr;
// low번째 점과 high번째 점 사이 거리를 구한다
int Distance(int low, int high){
	int lowX = arr[low].first, lowY = arr[low].second;
	int highX = arr[high].first, highY = arr[high].second;
	
	int disX = highX - lowX, disY = highY - lowY;
	
	return disX * disX + disY * disY;
}

// 가장 가까운 두 점의 거리를 구하는 재귀함수를 이분 탐색을 통해 구현한다
int BinarySearch(int low, int high){
	// 기저 조건은 처음과 끝 숫자의 차이가 1인 경우다
	if(low == high)
		return MAX;
	
	if(low + 1 >= high)
		return Distance(low, high);
	
	int disMin = Distance(low, high);
	int tempDis = 0, mid = (low + high) / 2;
	
	// 왼쪽 영역의 최소 거리를 구하고
	if((tempDis = BinarySearch(low, mid)) < disMin){
		disMin = tempDis;
	}
	// 오른쪽 영역의 최소 거리를 구하여 둘 중 최솟값을 찾는다
	if((tempDis = BinarySearch(mid + 1, high)) < disMin){
		disMin = tempDis;
	}	
	
	vector<pair<int, int>> inner;
	// 중간 영역에서 기준선과 x값의 차이의 제곱이 최솟값 이하인 영역의 점들을 찾는다
	int lineX = arr[mid].first;
	// 왼쪽 영역
	for(int i=mid; i>=low; i--){
		int x = arr[i].first, dist = lineX - x;
		if(disMin <= dist * dist) break;
		inner.push_back({arr[i].second, arr[i].first});
	}
	// 오른쪽 영역
	for(int i=mid+1; i<=high; i++){
		int x = arr[i].first, dist = lineX - x;
		if(disMin <= dist * dist) break;
		inner.push_back({arr[i].second, arr[i].first});
	}
	
	int len = inner.size();
	// 아무 점도 못찾았으면 최솟값을 반환한다
	if(len == 0) return disMin;
	// y값에 대해 정렬한다
	sort(inner.begin(), inner.end());
	
	for(int i=0; i<len; i++){
		int iX = inner[i].second, iY = inner[i].first;
		for(int j=i+1; j<len; j++){
			int jX = inner[j].second, jY = inner[j].first;
			int distX = jX - iX, distY = jY - iY;
			// 두 점의 y좌표의 차이를 제곱한 값이 최솟값 이상이면 loop를 멈춘다
			if(disMin <= distY * distY) break;
			// 두 점의 x좌표의 차이를 제곱한 값이 최솟값 이상이면 건너뛴다
			if(disMin <= distX * distX) continue;
			
			int dist = distX*distX + distY*distY;
			if(dist < disMin)
				disMin = dist;
		}
	}
	
	return disMin;
}

int main(){
	scanf("%d",&N);
	
	arr = vector<pair<int, int>>(N);
	
	for(int i=0; i<N; i++){
		scanf("%d %d", &arr[i].first, &arr[i].second);
	}
	
	sort(arr.begin(), arr.end());
	
	printf("%d \n", BinarySearch(0, N-1));
}

Result

• 두 점의 x값의 차이가 최솟값보다 큰 점들만 제외하여 계속 시간 초과가 발생하였다.
• 두 점의 y값의 차이까지 고려하여 알고리즘을 짜니 시간 복잡도를 크게 줄일 수 있었다.