백준 2261 - 가장 가까운 두 점, C++, Closest Pair, 분할정복

2261번: 가장 가까운 두 점

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct Point{
    int x;
    int y;

    bool operator < (const Point &b) const{
        if(x == b.x)
            return y < b.y;
        else
            return x < b.x;
    }
};

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

bool CompareY(Point a, Point b){
    return a.y < b.y;
}




int SearchAll(vector<Point> &v,int s, int e){
    int minDist = -1;

    for(int i = s; i <= e - 1; i++){
        for(int j = i + 1; j <= e; j++){
            int dist = Distance(v[i], v[j]);

            if(minDist == -1 || minDist > dist)
                minDist = dist;
        }
    }

    return minDist;
}



int SearchPoint(vector<Point> &v, int start, int end){
    int count = end - start + 1;

    if(count <= 3)
        return SearchAll(v, start, end);
    
    int mid = (start + end) / 2;
    int left = SearchPoint(v, start, mid);
    int right = SearchPoint(v, mid + 1, end);

    int answer;
    if(left > right)
        answer = right;
    else
        answer = left;

    // 중앙 근처 값을 계산할 예정
    vector<Point> final;

    for(int i = start; i <= end; i++){
        int xDistance = v[i].x - v[mid].x;

        if(xDistance * xDistance < answer)
            final.push_back(v[i]);
    }
    
    // y 기준 정렬
    int maxIndex = final.size();
    sort(final.begin(), final.end(), CompareY);

    for(int i = 0; i < maxIndex - 1; i++){
        for(int j = i + 1; j < maxIndex; j++){
        
            int y = final[j].y - final[i].y;

            if(y*y < answer){
                int dist = Distance(final[j], final[i]);
                if(dist < answer)
                    answer = dist;
            }
            else 
                break;
        }
    }
    return answer;
}


int main(){
    int n;
    cin >> n;
    vector<Point> points(n);

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


    int answer = SearchPoint(points, 0, n-1);

    cout << answer << '\n';
}

---

 학교 알고리즘 과제로 인해 풀이하게 된 문제입니다. 이 문제를 푸는 방법이 라인 스위핑과 분할정복이 있는데 라인 스위핑을 모르기도 하고 이번에 분할정복을 배우면서 푸는 문제라 분할정복으로 문제를 풀이 했습니다.

 

 위 코드의 컨셉은 아래와 같습니다.

 

- 먼저 x 축을 기준으로 정렬을 해준 뒤 그룹을 절반으로 분리합니다.

- 그룹의 점 수가 3보다 크다면 중간점을 잡고 다시 분리를 합니다.

- 그룹의 점 수가 3개 이하라면 브루투포스를 통해 모든 점들간 거리를 계산해보고 제일 작은 지점을 뽑습니다.

- 모든 그룹을 분할한 뒤 각 그룹의 최솟값을 구했다면 2개씩 그룹을 합칩니다.

- 그룹을 합치는 동안 그룹 중 가장 거리가 짧은 길이를 저장합니다.

- 이후 이 거리를 d라고 했을 때 두 그룹의 중간지점에서 x, y축으로 d 안에 있는 점들의 거리를 재고 d보다 짧은 점이 있다면 그 값으로 업데이트 해 줍니다.

 

 

개인적으로는 마지막의 조합을 알기가 힘들어 코드 구현하는데 어려움이 있었습니다.