[종만북] 문제: MINASTIRITH
문제
$(0,0)$을 중심으로 하는 반지름 $8$인 원 $C$가 있다.
$n$개의 원 $C’$의 좌표와 반지름 $y_i, x_i, r_i$이 추가로 제공된다.
추가로 제공되는 원 $C’$로 원 $C$의 둘레를 전부 감싸려고 할 때, 최소로 필요한 $C’$의 개수를 구하시오, 단, 구할 수 없으면 IMPOSSIBLE를 출력한다.
원 $C’$의 중심은 원 $C$의 둘레에 위치한다.
서론
이번에는 모든 선택지를 고려해보고 전체 답이 좋은 방법을 선택하는 것이 아닌, 각 단계마다 최선의 방법을 선택하는 그리디 알고리즘을 알아보려합니다.
그리디 알고리즘은 최적해를 얻을 수 있는 접근이 직관적이지 않을 수도 있어서 실수에 유의해야 합니다.
따라서 알고리즘의 정당성을 증명하는 과정을 거치면 좋습니다.
그리디 알고리즘은 두 가지 속성을 증명하면 됩니다.
- 탐욕적 선택 속성 증명
- 최적 부분 구조 증명
탐욕적 선택 속성 증명
각 단계에서 탐욕적인 선택이 손해를 볼 일이 없다는 것을 증명하면 됩니다. 보통 귀류법으로 증명합니다.
최적 부분 구조 증명
각 단계에서 탐욕적인 선택이 전체 문제의 최적해를 얻을 수 있음을 보이면 됩니다.
이 속성은 웬만한 경우, 자명해서 증명할 필요가 거의 없지만, 예외적인 상황도 존재합니다.
ex) 첫 번째 선택을 하고 나서 남는 부분 문제는 최적이 아닌 방법(그리디 알고리즘 x)로 풀어야 할 때
알고리즘 구상
쉽게 만들기
일단 문제를 쉽게 만들어 봅시다. 원 $C’$는 결국 원 $C$의 호와 일치한다는 것입니다.
호는 원의 중심각이랑 관련이 있으니, 이 문제는 중심각 구간 $[0, 2\pi]$을 커버하는 문제로 쉽게 변형할 수 있습니다.
$[0, 2\pi]$를 보면, 구간이 떠오르지 않나요? 따라서 선분 커버 문제로 쉽게 변형이 가능합니다.
다만, 원이기 때문에 순환 구조를 가지고 있다는 점을 유의해야 합니다. (이를 순환 선분 커버 문제라고 합니다.)
선분 커버 문제
선분 커버 문제(Segment Cover Problem)는 주어진 선분들로 특정 구간을 완전히 덮을 수 있는 최소한의 선분 집합을 찾는 문제입니다.
$S = { [a_1, b_1], [a_2, b_2], \dots, [a_n, b_n] }, (a_i \leq b_i)$
$[L, R] \subseteq \bigcup_{i \in S’} [a_i, b_i]$
여기서 $S’$를 찾는 문제로 정의됩니다.
선분 커버 문제 풀이 절차
- 시작점 $a_i$을 기준으로 오름차순 정렬합니다.
- 초기 값을 $\text{current_end} = L$로 설정합니다.
- $a_i \leq \text{current_end}$를 만족하는 선분 중 끝점 $b_i$가 가장 큰 선분을 선택합니다.
- $\text{current_end} = b_i$ 이후, 3번 과정을 반복합니다.
- $\text{current_end} ≥ R$이면 종료, 확장되지 않으면(3번을 만족하는 선분이 존재하지 않으면) 선분 커버에 실패합니다.
정도의 절차를 가지고 있습니다.
이 알고리즘의 대한 증명은 귀류법으로 쉽게 증명이 가능하니 스킵하도록 하겠습니다.
알고리즘 구현
선분 커버 문제로 변환
원 $C’$의 정점이 가지는 중심각을 $\theta_{mid}$라 하고, 이 후 원 $C’, C$의 정점, $C’$와 $C$의 접점이 가지는 중심각을 $\theta_{delta}$로 정의합니다.
$\theta_{mid} = \arctan\left(\frac{y}{x}\right)$
수학 공식을 이용하여,
$\theta_{delta} = 2 \times \arcsin(\frac{r}{2 \times 8})$로 쉽게 정의할 수 있습니다. 이등변삼각형의 정의를 변형한 것입니다.
$a_i = \theta_{mid} - \theta_{delta}, b_i = \theta_{mid} + \theta_{delta}$로 선분 커버 문제로 변환이 가능합니다.
구현은 <cmath>의 atan2(x, y)와 asin(x, y)을 이용합니다.
atan2(x, y)의 범위는 $[-\pi, \pi]$입니다. 값을 관리하게 편하게 $[0, 2\pi]$로 변환해줍니다.
이후 값을 관리하고 정렬하기 쉽게 pair<double>을 이용해 구현합니다.
1
2
3
4
5
6
7
8
9
10
11
vector<pair<double, double>> arcs(n);
bool singleOk = false;
for (int i = 0; i < n; i++) {
double y, x, r;
cin >> y >> x >> r;
if (r >= 16.0) singleOk = true;
double mid = fmod(atan2(x, y) + 2.0 * M_PI, 2.0 * M_PI);
double delta = 2.0 * asin(r / 16.0);
arcs[i] = make_pair(mid - delta, mid + delta);
}
sort(arcs.begin(), arcs.end());
문제를 분리하기
순환 선분 커버 문제이기 때문에, 순환에 대한 부분을 따로 분리합니다.
구간이 $[0, 2\pi]$이기 때문에, 이 순환 구간의 양 끝에 존재하는 선분이 있다는 것을 고려하는 알고리즘이 있어야 합니다.
$\theta_{delta}$를 빼거나 더해서 $a_i$, $b_i$를 구하기 때문에 이 값이 $0$보다 작거나, $2 \pi$보다 크다면 순환 지점 0에 걸쳐 있는 것이죠.
따라서 0을 덮는 선분$[a_i, b_i]$을 하나 택해서 순환 선분 커버 문제가 아닌,
$[b_i \bmod 2\pi, (a_i + 2\pi) \bmod 2\pi]$의 선분 커버 문제로 변형 시킬 수 있습니다.
이후에는 위에 서술한 선분 커버 문제를 푸는 알고리즘을 이용해 문제를 풉니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int ans = 111111111;
bool anySuccess = false;
for (int i = 0; i < n; i++) {
if (arcs[i].first <= 0 || arcs[i].second >= 2.0 * M_PI) {
bool localCover = true;
double begin = fmod(arcs[i].second, 2.0 * M_PI);
double end = fmod(arcs[i].first + 2.0 * M_PI, 2.0 * M_PI);
int used = 1, idx = 0;
while (begin < end) {
double mx = -1;
while (idx < n && arcs[idx].first <= begin) {
mx = max(mx, arcs[idx].second);
idx++;
}
if (mx <= begin) {
localCover = false;
break;
}
begin = mx;
used++;
}
if (localCover) {
anySuccess = true;
ans = min(ans, used);
}
}
}
최종 코드
여기에서 확인하세요!