볼록 껍질
백준 1708
PLATINUM V
문제 내용
문제 링크
해결 방안
문제에서 이름처럼 볼록 껍질의 정의를 설명해주고, 그 볼록 껍질을 이루는 점의 개수를 찾는 문제이다. 볼록 껍질을 찾는 알고리즘은 계산기하(computational geometry)라는 컴퓨터 과학에서 기하학에 대한 알고리즘을 다루는 분야로 분류되어 있다. 그만큼 볼록 껍질을 찾는 다양한 알고리즘이 연구되어 왔지만, 이번 문제에서는 그 중에서도 그레이엄 스캔 알고리즘(Graham Scan)을 사용하여 풀이하고자 한다.
그레이엄 스캔 알고리즘의 작업 수행 단계는 다음과 같다.
- y 좌표 값이 가장 작은, 그 중에서도 x 좌표 값이 가장 작은 기준점을 찾는다.
- 기준점을 제외한 점들을 기준점으로부터 x축에 대해 각도 증가하는 순으로 정렬한다. 다시 말해, 기준점에 대해 반시계 방향으로 회전하는 점이 앞으로 오도록 점들을 정렬한다.
- 각 정렬된 점들을 순회하면서 앞의 두 점과 해당 점을 이었을 때, 좌회전하는 지 우회전하는 지를 확인한다. 만약 우회전하면, 가운데의 점이 볼록 껍질 안에 있는 점이라는 것이므로 해당 점을 제외하고 점을 다시 탐색한다. 이를 통해 점들을 이어 다각형을 만들었을 때, 만들어질 다각형이 볼록 다각형인지 오목 다각형인 지를 판별할 수 있다.
- 모든 정렬된 점에 대해 좌회전 혹은 우회전에 대한 판정이 끝나면, 좌회전하는 모든 점들이 볼록 껍질의 꼭짓점에 해당한다.
각 점이 좌회전하는 지, 즉 x축에 대해 각도가 증가하는 방향인지를 확인하기 위해, 본래라면 각각의 각도가 x축에 대해 양수인지 음수인지를 판별할 필요가 있다. 하지만, 우리에게 필요한 것은 정확한 각도가 아닌 두 선분이 이루는 방향이다. 방향을 알기 위해서는 각도를 구하는 대신 두 벡터가 이루는 외적의 z좌표를 구하고, 그 벡터가 양수인지 음수인지만 판별하면 된다.
각도를 알고자 하는 세 점을 각각 P₁=(x₁, y₁), P₂=(x₂, y₂), P₃=(x₃, y₃)라고 할 때, P₁P₂가 이루는 벡터와 P₁P₃가 이루는 벡터의 외적의 z좌표는 (x₂ - x₁)(y₃ - y₁) - (y₂ - y₁)(x₃ - x₁)이다. 이 외적의 z좌표가 양수라면 x축에 대해 각도가 증가하는 방향인 좌회전(반시계 방향으로 회전)하는 것이고, 반대로 음수라면 x축에 대해 각도가 감소하는 방향인 우회전(시계 방향으로 회전)하는 것임을 알 수 있다.
결과적으로, 그레이엄 스캔 알고리즘의 시간 복잡도는 과정 1에서 O(N), 과정 2에서 O(Nlog₂N), 과정3에서 O(N)이므로 종합적인 시간 복잡도는 정렬할 때의 필요한 시간인 O(Nlog₂N)이다.
볼록 껍질(convex hull)이란?
볼록 껍질(convex hull)은 유클리드 공간에서 정의된 바에 따르면, 임의의 점 집합에 대해 집합의 점들을 골라 서로 잇는 것으로 나머지 모든 점들을 내부에 포함시키는 볼록 다각형을 말한다. 여기서 볼록 다각형이란 모든 내각이 180도 이내이면서, 임의의 변을 연장해도 다각형의 내부를 지나지 않는 다각형을 의미한다. 정리하면, 임의의 점들이 주어졌을 때, 그 점들을 이어 각 내각이 180도 이내이면서 모든 점들을 감싸는 도형을 볼록 껍질이라고 부르는 것이다.
볼록 껍질에 관한 문제들은 이러한 볼록 껍질을 찾는 것과 관련된 다양한 알고리즘을 사용하는 문제다. 볼록 껍질을 찾기 위한 알고리즘으로는 분할 정복을 이용한 알고리즘부터 선물 포장 알고리즘, 퀵 소트를 이용한 알고리즘 등등 다양한 방법이 있다. 이번 문제에서는 이러한 알고리즘에서도 그레이엄 스캔 알고리즘을 사용하여 풀이하도록 한다.
풀이 코드
#include <iostream>
#include <vector>
#include <algorithm>
#define ft first
#define sd second
using namespace std;
using lli = long long int;
// 각 점의 2차원 좌표계에 대한 자료형
using coord = pair<lli, lli>;
// 점의 개수
int n;
// 각 점의 좌표
vector<coord> pos;
// 각 점 중 볼록 껍질에 해당하는 점 탐색
vector<coord> stack;
// CCW 알고리즘(Counter Clock Wise)
// 두 벡터의 외적을 풀어서 나타낸 식을 반환
lli ccw(coord a, coord b, coord c) {
return (a.ft * b.sd) + (b.ft * c.sd) + (c.ft * a.sd)
- ((b.ft * a.sd) + (c.ft * b.sd) + (a.ft * c.sd));
}
// 반시계 방향으로 정렬하기 위한 비교 함수(comparison function)
bool compare(coord a, coord b) {
// 기준점과 두 점이 반시계 방향인지 확인
lli cc = ccw(pos[0], a, b);
// cc가 0이 아니면 cc가 작은 순
if(cc)
return cc > 0;
// 각도가 0이면 y 값이 작은 순
if(a.sd != b.sd)
return a.sd < b.sd;
// 그 외에는 x 값이 작은 순 정렬
return a.ft < b.ft;
}
// 두 좌표를 교체하는 함수
void swap(coord &a, coord &b) {
coord tmp = a;
a = b;
b = tmp;
}
int main() {
// Fast I/O
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(false);
// 점의 개수와 점의 각 좌표를 입력
cin >> n;
pos = vector<coord>(n);
for(int i = 0; i < n; i++)
cin >> pos[i].ft >> pos[i].sd;
// 볼록 껍질을 찾기 시작하는 기준점 설정
// y 좌표가 가장 작은 점을, y 좌표가 같다면 x 좌표가 가장 작은 점을 기준
for(int i = 1; i < n; i++) {
if(pos[i].sd < pos[0].sd)
swap(pos[i], pos[0]);
else if(pos[i].sd == pos[0].sd && pos[i].ft < pos[0].ft)
swap(pos[i], pos[0]);
}
// 기준점을 제외한 모든 기준점에 대해 반시계 방향으로 정렬(CCW 함수 사용)
sort(++pos.begin(), pos.end(), compare);
// 기준점과 다음 순서 저장
stack.push_back(pos[0]);
stack.push_back(pos[1]);
// 기준점부터 시작하여,
coord top, sub_top;
for(int i = 2; i < n; i++) {
// 최소한 두 점이 있을 때, 판별할 수 있음
while(stack.size() >= 2) {
// 맨 위의 두 점과 현재 점과의 관계 확인
sub_top = stack.back();
stack.pop_back();
top = stack.back();
// 현재 점에 대해 볼록 다각형이 만들어 질 수 있으면,
// 맨 위의 두 점을 원래대로 되돌림
if(ccw(top, sub_top, pos[i]) > 0) {
stack.push_back(sub_top);
break;
}
// 현재 점과 볼록 다각형이 만들어지지 않으면,
// 가운데의 점(sub_top)이 볼록 다각형 안의 점이라는 것이므로 제외함
}
// 현재의 점을 추가
stack.push_back(pos[i]);
}
// 만들어진 볼록 다각형의 꼭짓점 개수 출력
cout << stack.size() << endl;
return 0;
}