2261 백준 - 가장 가까운 두 점, 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;
    char temp; // 쉼표 제거용
    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';
}

---

 학교 과제에 나와 백준에 비슷한 문제를 찾다 발견한 문제입니다. 라인스위핑과 분할정복 2가지 방법으로 풀 수 있다고 하는데 저같은 경우 강의에서 배운 내용이 분할정복이라 분할정복으로 풀이를 했습니다.

 알고리즘의 핵심은 아래와 같습니다.

 

- 점들의 집합이 있다면 가운데 점을 기점으로 해서 왼쪽, 오른쪽으로 나눈다

- 나누었다면 나눠진 곳에서 가장 짧은 길이를 구해 이를 dl, dr 이라고 한다.

- min(dl, dr) 로 나온 값을 구한 뒤 분할에 사용된 가운데 점에서 min(dl, dr) 만큼 떨어진 점들을 탐색을 한다

- 가운데 점에서 min(dl, dr) 만큼 x, y 축으로 가까이 있는 점들만 탐색을 하면 된다. 그 이상은 최솟값이 될 수 없다.

 

- 위 알고리즘의 분할 정복에서 최소 집합의 원소 수는 2~3개 이다.

  3개 까지만 나눠져도 수월하게 구할 수 있다 (위 코드에서는 SearchAll 함수)

 

위 코드에 있는 char temp같은 경우 과제를 위해 만들어둔 변수라 무시해도 됩니다.

 

코드 설명을 정말 간략하게 남겨둔다면

- SearchAll : 분할을 한 결과 원소가 2개 또는 3개라면 완전 탐색을 통해서 가장 짧은 길이를 찾는 것입니다.

- SearchPoint : 분할 정복을 하는 함수로 min(dl, dr) 보다 x축으로 멀지 않은 점들을 임시 벡터에 넣어서 이후 y 축 정렬을 통해 정렬을 한 뒤 min(dl, dr)보다 y 축 거리가 짧다면 거리 계산을 해주는 함수입니다.