문제

풀이

Reference에서 코드를 가지고 왔다.
알고리즘이 상당히 복잡하다. 먼저, O(N^2)으로 하면 시간초과가 나는 문제이다. 시간초과를 면하기 위해서 알고리즘들이 추가가 되는데 알고리즘은 다음과 같다.

x축으로 정렬된 값 중 start와 end의 중간값인 mid를 기준으로 왼쪽 오른쪽 구간으로 나눈다. 이 구간에서 distance_min을 각각 찾고 최종적으로 두 개 중 더 작은 distance_min을 채택한다.
1-1. 이 때, 1개의 점만 있는 경우는 두 점 사이의 거리를 구할 수 없으므로 3개의 점이하일 때, O(N^2)의 bruteforce방법으로 distance_min을 찾으면 된다.
경계로 나누었을 때, 경계 근방에 서로 다른 영역에 있는 점들이 distance_min이 될 수 있으므로 이 영역을 구하기 위한 알고리즘을 짠다.
2-1. 먼저 mid에서 distance_min만큼 떨어진 곳들만 candidate 점들로 채택한다.
2-2. candidate 점들을 y축으로 정렬하여, 점들을 모두 탐색하는데, 역시 y축에서 distance_min내에 떨어진 점들만 distance를 구해서 그 거리가 기존의 min값보다 작으면 min값을 갱신하여 계속해서 탐색해나간다.
결과적으로, O(NlogN)의 시간복잡도를 가진다.

소스 코드

#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 800000000;

int n;
vector<pair<int, int>> v;

int f(int, int);
int dist(pair<int, int>, pair<int, int>);

int main() {
  scanf("%d", &n);
  v.resize(n);
  for (int i=0; i<n; i++) {
    scanf("%d %d", &v[i].first, &v[i].second);
  }
  sort(v.begin(), v.end());// x축을 기준으로 오름차순 정렬
  printf("%d\n", f(0, n-1));
  return 0;
}

int f(int start, int end) {
  int ret = MAX;
  int ec = end - start + 1;// element count
  if (ec <= 3) {
    for (int i=start; i<end; i++) {
      for (int j=i+1; j<=end; j++) {
        ret = min (ret, dist(v[i], v[j]));
      }
    }// brute-force
  }
  else {
    // 중앙 좌표를 기준으로 왼쪽과 오른쪽 섹션을 분할하여 계산
    int mid = (start + end) / 2;
    int left = f(start, mid-1);
    int right = f(mid+1, end);
    ret = min(left, right);

    vector<pair<int, int>> tmp;
    tmp.push_back({v[mid].second, v[mid].first});

    // 중앙 좌표를 중심으로 왼쪽에 있는 것들 중 가능한 것들을 선별
    for (int i=mid-1; i>=start; i--) {
      if (dist({v[mid].first, 0}, {v[i].first, 0}) >= ret) break;
      tmp.push_back({v[i].second, v[i].first});// y축 순으로 정렬
    }

    // 중앙 좌표를 중심으로 오른쪽에 있는 것들 중 가능한 것들을 선별
    for (int i=mid+1; i<=end; i++) {
      if (dist({v[mid].first, 0}, {v[i].first, 0}) >= ret) break;
      tmp.push_back({v[i].second, v[i].first});// y축 순으로 정렬
    }

    sort(tmp.begin(), tmp.end());// y축 정렬

    // 중앙 좌표와의 거리 중 더 가까운 좌표가 있다면 그 거리를 반환
    for (int i=0; i<tmp.size()-1; i++) {
      for (int j=i+1; j<tmp.size(); j++) {
        if (pow(tmp[i].first - tmp[j].first, 2) >= ret) break;
        ret = min(ret, dist(tmp[i], tmp[j]));
      }
    }
  }
  return ret;
}

int dist(pair<int, int> p1, pair<int, int> p2) {
  return pow(p1.first - p2.first, 2) + pow(p1.second - p2.second, 2);
}

[BOJ] 2261번 가장 가까운 두 점 - C++

"정렬"

문제

풀이

소스 코드

CATALOG

FEATURED TAGS