1. boj 1319, 지민 VS 한수.
이전에 소개한 sweeping 테크닉을 응용해서 기하학 문제를 풀어보자.
스위핑에 대해서 알고싶다면 이전 글을 참고!
1) 문제 개요
해당 문제(지민vs한수)는 boj 골드 2 문제로, 나를 대단히 괴롭혔기에 경의를 담아서 풀이를 소개한다. 앞서 80k 코딩경에 sweeping 테크닉에 대해서 소개한 바도 있기에 연계해서 읽어보면 도움이 될 것으로 생각한다.
해당 문제는 과수원에 존재하는 과실수를 최대한 공평하게(즉 과실수의 가치 차이가 최소가 되도록) 분할하는 문제이다. 과수원은 하나의 평면이고, 평면 상에 과실수가 여럿 흩어져 있다. 이 과수원은 하나의 직선으로 분할되어야 한다. 문제의 입력으로 과실수들의 위치좌표와 가치가 주어진다. 분할한 과수원의 나무 가치의 차이를 출력한다.
문제를 분석했을 때, 과수원이 직선으로 분할된다는 점, 또한 과수원을 구성하는 나무의 가치의 합을 구해야 한다는 점에서 누적 합을 떠올렸고, sweep 테크닉을 사용해야 한다고 생각했다. 다만, 연속된 평면 속에서 어떻게 sweep line을 구성해야 할지가 감이 오지 않아 많은 시행착오가 있었다. 여러 조언을 받고, 실패를 거듭하여 얻은 풀이는 주어진 점들의 집합에서 두 점을 선택해서 분할선을 얻고, 이 선을 평행이동하며 과수원을 분할하는 것이다. 즉 두 점에서 얻은 직선의 기울기를 기준으로 sweep line을 구성하는 것이다.
분할선을 순차적으로 평행 이동하며 sweeping을 수행해야 하므로, 점의 정렬 기준을 기준선에서 떨어진 거리로 정의한다. 이 때 직선으로부터 떨어진 거리는 외적(cross product)을 통해서 구할 수 있다. 해당 정렬에서는 필연적으로 기준이 되는 직선에서 떨어진 거리는 같지만, 서로 다른 점들에 대해서 예외가 발생한다. 이는 평면이 직선으로 분할되어야 한다는 조건에 의한 것으로, sweeping을 위해서는 이들 점에 대해서도 순서대로 방문할 수 있어야 한다. 따라서, 내적(dot product)을 통해서 우선순위를 달리하도록 구성한다.
2) 풀이
문제의 풀이는 다음과 같다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
#include <queue>
using tree = std::tuple<int, int, int>; // 방문의 대상이 되는 과실수 x, y, value
std::vector<tree> trees; // tree 정보를 저장하는 버퍼
std::vector<int> index_buffer; // trees의 인덱스들, 트리 대신 정렬됨
int pivot_x, pivot_y; // pivot 점의 좌표
int div_x, div_y; // 공간을 이분하는 div line의 방향벡터
int dot(const int &idx) // 공간을 이분하는 div 라인 위에서의 위치 정도
{
const int x = std::get<0>(trees[idx]) - pivot_x;
const int y = std::get<1>(trees[idx]) - pivot_y;
return (div_x * x + div_y * y);
}
int cross(const int &idx) // 공간을 이분하는 div 라인에서 떨어진 정도, div 라인의 평행이동
{
const int x = std::get<0>(trees[idx]) - pivot_x;
const int y = std::get<1>(trees[idx]) - pivot_y;
return (x * div_y - y * div_x);
}
bool cmp_index_cw(const int &idx1, const int &idx2)
{
int priority1 = cross(idx1);
int priority2 = cross(idx2);
if (priority1 == priority2)
{
priority1 = dot(idx1);
priority2 = dot(idx2);
return (priority1 < priority2); // 내적 결과 오름차순
}
return (priority1 < priority2); // 외적 결과 오름차순
}
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int N, total_value = 0, min_gap = 6e7;
// 입력
std::cin >> N;
for (int i = 0; i < N; ++i)
{
int x, y, val;
std::cin >> x >> y >> val;
total_value += val;
trees.push_back(std::make_tuple(x, y, val));// 나무를 튜플로 저장함
index_buffer.push_back(i);
}
// 두 나무를 선택, 두 나무를 잇는 직선의 기울기를 공간을 이분하는 div line의 기울기로 삼는다
for (int pivot_idx = 0; pivot_idx < N - 1; ++pivot_idx)
{
// pivot point, 두 점 중 기준
pivot_x = std::get<0>(trees[pivot_idx]);
pivot_y = std::get<1>(trees[pivot_idx]);
for (int target_idx = pivot_idx + 1; target_idx < N; ++target_idx)
{
// div line의 방향벡터를 획득
div_x = std::get<0>(trees[target_idx]) - pivot_x;
div_y = std::get<1>(trees[target_idx]) - pivot_y;
// divding line을 기준으로 점들을 정렬
//
std::sort(index_buffer.begin(), index_buffer.end(), cmp_index_cw);
int sum = 0, cur_min_gap = total_value;
// sweeping 수행
for (int idx_idx = 0; idx_idx < N; ++idx_idx)
{
sum += std::get<2>(trees[index_buffer[idx_idx]]);
int cur_gap = std::abs(total_value - sum * 2);
if (cur_min_gap < cur_gap) // 차이가 도리어 증가한다면 멈춤
{
break;
}
cur_min_gap = cur_gap;
}
// get minimum gap value
min_gap = std::min(min_gap, cur_min_gap);
}
}
std::cout << min_gap;
}
C++
복사
풀이 과정에서 특기할 점이라면, 점들을 정렬하지 말고, 그 점들을 가리키는 index를 대신 정렬한다는 점이다. 이는 다수의 sorting이 발생하는 문제의 특성상, tuple의 swap은 상당히 비싸기 때문이다. 따라서 별도의 index buffer를 두고, 이를 정렬한 다음, index를 이용해서 tuple의 벡터에 접근하도록 구현하였다.
나무의 수를 N이라 했을 때, 해당 풀이의 시간 복잡도는 다음과 같다.
이는 sweeping 테크닉의 특성 상, 정렬이 가장 dominant 한 영향을 미치기 때문이다.
