[백준 2261] 가까운 두 점 찾기 - Sweep line Algorithm

참고: www.acmicpc.net/blog/view/25

가장 가까운 두 점 찾기

 

 

너무나도 까다로운 문제였습니다. 분할정복으로도 풀 수 있으나, 백준님의 해설을 따라서 Sweep-line algorithm으로 해결해 보았습니다.

 

먼저 이 문제는 1초의 시간제한을 가지고 있기 때문에 모든 점을 서로 비교하는 방법의 O(n^2)의 시간으로 풀 수 없습니다.

그렇기에 O(nlog n)의 Sweep-line algorithm을 사용하였습니다.

 

코드의 실행 순서는 다음과 같습니다.

1. Point를 x 크기 순으로 정렬합니다.

2. dist(a[0], a[1])을 최소값으로 먼저 설정하고, pivot이라고 할 수 있는 a[2] 와 비교합니다. 

3. a[0] 와 a[2]의 x 거리를 비교한 dx가 ans (정답 길이)보다 길다면 후보군에서 뺍니다. 

4. 이 과정을 반복해 x의 정답 길이 안 쪽에 있는 후보군을 추출합니다. 

다음과 같이 x 길이로 후보군을 추출했으니 이제 y 값으로 최소 길이를 찾을 차례입니다.

5. upper bound, lower bound로 y값의 차이가 d 이하인 후보군들의 길이를 서로 비교합니다. 

6. 이 과정이 끝나면, pivot을 후보군에 넣고, pivot을 전진시킵니다.

7. 위 과정을 반복합니다. 

 

이 논리대로 문제를 풀이하는 경우 O(2NlogN)의 시간복잡도를 가지게 되어 시간 초과가 나게 됩니다. 

이를 해결하는 방법으로 2가지가 있습니다.

 

1. set 자료구조를 이용해서, 입력 단계에서 y값의 순서를 지켜주어, y값의 정렬을 하지 않습니다.

또한 set은 삽입, 삭제, 탐색이 모두 O(lgN)이 걸리기 때문에, O(NlgN)이라는 시간으로 가장 가까운 두 점을 구할 수 있습니다.

 

2. while(start - i)

for (auto it = candidate.begin(); it!=candidate.end(); ) {
            auto p = *it;
            int x = now.x - p.x;
            if (x*x > ans) {
                it = candidate.erase(it);
            } else {
                it++;
            }

 만약 다음과 같이 코드를 작성했다고 한다면 굉장한 시간 낭비입니다. set은 x가 아닌 y순으로 정렬되어있기 때문에 필요없는 순회를 많이 해야합니다.

while (start < i) {
            auto p = a[start];
            int x = now.x - p.x;
            if (x*x > ans) {
                candidate.erase(p);
                start += 1;
            } else {
                break;
            }
        }

하지만 다음과 같이 수정해준다면 (a는 vector<Point>) 반복자로 순회하며 제거하는 것이 아니라 set의 제거 즉 lgN 타임에 해결할 수 있으므로, 속도가 올라갑니다.

 

 

전체 코드는 다음과 같습니다.

#pragma warning (disable: 4996)
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

struct Point {
	int x, y;
	Point() {
	}
	Point(int x, int y) : x(x), y(y) {
	}
	// set 등 자동으로 대소비교를 해주는 STL에서 구조체/클래스 등의 타입을 넣어주었을 때 발생하는 에러
	// 내부에서 데이터를 가지고 비교해야하는데 구조체 타입이기 때문에 연산을 할 수 없다.
	// 이를 해결하기 위해서 내부 정렬을 위한 방법을 지정해주면 된다.
	// 아래에서는 y값 순서대로 비교할 수 있게 하였다.
	bool operator < (const Point &v) const {
		if (y == v.y) {
			return x < v.x;
		}
		else {
			return y < v.y;
		}
	}
};
// x 값 비교
bool cmp(const Point &u, const Point &v) {
	return u.x < v.x;
}

// 두 점 사이 거리 제곱
int getDist(Point p1, Point p2) {
	return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
}

int main() {
	int n;
	scanf("%d", &n);
	vector<Point> a(n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &a[i].x, &a[i].y);
	}
	sort(a.begin(), a.end(), cmp); // x 커지는 순으로 정렬
	set<Point> candidate = { a[0], a[1] };
	int ans = getDist(a[0], a[1]); // 처음 최소값은 0번 1번 거리로
	int start = 0;
	// candidate가 0번 1번으로 시작하니까 p는 2번부터 시작
	for (int i = 2; i < n; i++) {
		Point now = a[i];
		// 정해진 now를 기준으로 후보군과 길이 비교해서, 후보군 추리기
		while(start < i) {
			auto p = a[start];
			int dx = now.x - p.x;
			// 직선 거리가 정답보다 길다면 아예 후보군에 넣을 필요가 없음 
			if (dx*dx > ans) {
				candidate.erase(p);
				start += 1; // 시작점 앞당기기
			}
			else
				break;
		}
		int d = (int)sqrt((double)ans) + 1; // 길이 보정
		auto lower_point = Point(-100000, now.y - d); // 좌측 하단 
		auto upper_point = Point(100000, now.y + d); // 우측 상단
		// 하한값 위치, 상한값 위치
		auto lower = candidate.lower_bound(lower_point);
		auto upper = candidate.upper_bound(upper_point);

		for (auto it = lower; it != upper; it++) {
			// x값으로 추려진 candidate에서 
			int d = getDist(now, *it);
			// 지속적으로 ans를 갱신
			if (d < ans)
				ans = d;
		}
		// 사용된 now 역시 다시 후보군으로
		candidate.insert(now);
	}

	printf("%d\n", ans);

	return 0;
}