[ 백준 / C++ ] 2261 : 가장 가까운 두 점

[ 문제 ]

 

2261번: 가장 가까운 두 점

 

[ 접근방법 ]

 

분할 정복을 활용하여 O(N log N)로 해결할 수 있다.

 

먼저, 입력된 n개 점들을 x값 기준으로 정렬한다.

그 후, 인덱스 "0 ~ n - 1" 범위의 점들에 대해 분할 정복을 적용하여 가장 가까운 두 점을 찾는다.

 

인덱스 "l ~ r" 범위의 점들에 대해 분할 정복을 적용하는 과정은 다음과 같다.

 

1. 인덱스 "l ~ r" 범위내에 점이 3개 이하로 있으면 브루트포스를 통해 값을 찾는다.

    4개 부터는 분할 정복을 적용하는게 더 빠르다( 그냥 r - l < 2 일때 두 점 비교해줘도 되긴함 ).

    이 후 범위내에 점들을 y값 기준으로 정렬하는데, 이는 4번 과정을 신속하게 진행하기 위해서이다.

 

2. 중간값 m을 기준으로 인덱스 "l ~ m", "m + 1 ~ r" 범위로 분할하고 최솟값 d를 찾는다.

    이 과정은 두 점이 한 영역에만 속해있을 때를 생각한 것이고, 두 영역 모두에 점이 있는 경우를 생각해야 한다.

    + 분할 정복 후 pts 벡터 내의 순서가 바뀔 수 있으므로 중간값 m의 x 좌표를 미리 변수에 저장해야 한다.

 

3. 각 영역에 점을 한개씩 뽑아서 모든 경우를 비교하는 것은 비효율적이다. 따라서 앞서 구한 d를 활용해야 한다.

    중간값 m의 x 좌표를 기준으로 x 좌표만 따졌을 때 거리값이 d 이하인 점들을 tmp 벡터에 저장한다.

    tmp 벡터내의 점들 중에 y 좌표만 따졌을 때 거리값이 d 이하인 점들만 거리값을 계산하여 d를 갱신한다.

 

4. 3번 과정중에 tmp 벡터가 y값 기준으로 정렬되어 있다면 계산량을 줄일 수 있다.

    매 과정마다 sort를 돌릴 수도 있지만( 정렬 시간 복잡도 O(N log N), 전체 시간 복잡도 O(N log² N)  ),

    분할하는 과정에서 미리 정렬을 한 후에 머지를 하면 더 빠르게 계산할 수 있다 ( 머지 시간 복잡도 O(N) ) .

 

[ 소스코드 ]

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

struct Point{
    int x, y;
};

bool cmpX(const Point &a, const Point &b){
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

bool cmpY(const Point &a, const Point &b){
    if(a.y != b.y) return a.y < b.y;
    return a.x < b.x;
}

int dist(const Point &a, const Point &b){
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

int f(vector<Point> &pts, int l, int r){
    if(r - l < 3){
        int d = INT_MAX;
        for(int i = l; i < r; i++){
            for(int j = i + 1; j <= r; j++){
                d = min(d, dist(pts[i], pts[j]));
            }
        }
        sort(pts.begin() + l, pts.begin() + r + 1, cmpY);
        return d;
    }

    int m = (l + r) / 2;
    int mx = pts[m].x;
    int d = min(f(pts, l, m), f(pts, m + 1, r));

    vector<Point> tmp;
    merge(
        pts.begin() + l, pts.begin() + m + 1,
        pts.begin() + m + 1, pts.begin() + r + 1,
        back_inserter(tmp), cmpY
    );
    copy(tmp.begin(), tmp.end(), pts.begin() + l);

    tmp.clear();
    for(int i = l; i <= r; i++){
        if((pts[i].x - mx) * (pts[i].x - mx) < d){
            tmp.push_back(pts[i]);
        }
    }

    for(int i = 0; i < tmp.size(); i++){
        for(int j = i + 1; j < tmp.size(); j++){
            if((tmp[i].y - tmp[j].y) * (tmp[i].y - tmp[j].y) < d){
                d = min(d, dist(tmp[i], tmp[j]));
            }
            else break;
        }
    }

    return d;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    vector<Point> pts(n);
    for(int i = 0; i < n; i++) cin >> pts[i].x >> pts[i].y;
    sort(pts.begin(), pts.end(), cmpX);

    cout << f(pts, 0, n - 1);

    return 0;
}