[C++ 백준 풀이][Platinum] 1708번 : 볼록 껍질 (Convex Hull 알고리즘)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 1708번 : '볼록 껍질' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 Platinum V에 해당하며, 문제를 풀이하기 위해 Convex Hull, 컨벡스 헐 알고리즘에 대해 다룰 것입니다.

 

 

1708번 : 볼록 껍질

 

2차원 좌표계로 N개의 점이 입력될 때, 이 점들 중 가장 큰 볼록다각형의 해당하는 점의 개수를 찾아서 출력하는 문제입니다.

단순히 보면 어렵지 않을 수도 있을 것이라는 생각이 들 수도 있지만, 기하적인 개념을 좌표계의 계산과 코드로 옮기는 과정이 생각보다 쉽지 않습니다.

점들을 정렬하고, 그 방향성을 정렬하는 데에 생각보다 많은 개념이 필요하며, 이것을 아래에서 다루겠습니다.

 

 

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
 
struct Coor { long long x, y; };
vector<Coor> Point;
 
long long CCW(Coor a, Coor b, Coor c) {
    return a.x*b.y + b.x*c.y + c.x*a.y - a.x*c.y - b.x*a.y - c.x*b.y;
}
 
bool minCCW(Coor a, Coor b) {
    long long Value = CCW(Point[0], a, b);
    if(Value) return Value > 0;
    else if(a.y != b.y) return a.y < b.y;
    else return a.x < b.x;
}
 
int main() {
    int N;
    Coor temp1, temp2;
    stack<Coor> Convex;
    scanf("%d", &N);
    Point.resize(N);
    for(int i=0; i<N; i++) scanf("%lld %lld", &Point[i].x, &Point[i].y);
    for(int i=1; i<N; i++) {
        if(Point[i].y < Point[0].y || (Point[i].y == Point[0].y && Point[i].x < Point[0].x)) {
            long long temp = Point[0].x;
            Point[0].x = Point[i].x;
            Point[i].x = temp;
            temp = Point[0].y;
            Point[0].y = Point[i].y;
            Point[i].y = temp;
        }
    }
    sort(Point.begin()+1, Point.end(), minCCW);
    Convex.push(Point[0]);
    Convex.push(Point[1]);
    for(int i=2; i<N; i++) {
        while(Convex.size() >= 2) {
            temp2 = Convex.top();
            Convex.pop();
            temp1 = Convex.top();
            if(CCW(temp1, temp2, Point[i]) > 0) {
                Convex.push(temp2);
                break;
            }
        }
        Convex.push(Point[i]);
    }
    printf("%d", Convex.size());
}
 

 

우선 벡터의 외적을 계산하기 위해 사선 공식을 써야 하기 때문에 구조체를 써서 변수명을 최대한 짧게 구성해 봤습니다.

먼저 점의 좌표를 하나의 구조체로 선언하고, 점들의 좌표를 모두 입력받아줍니다.

그 다음 가장 아래(가장 아래에 있는 점들이 여러 개라면 그 중에서 가장 왼쪽)에 있는 점을 0번 점으로 잡고(위 코드의 28~37행), 이 점으로부터 가장 왼쪽 아래에 있는 점을 1번, 그리고 나머지 점들은 0번 점과 1번 점을 이은 선분으로부터 반시계 방향으로 점들을 정렬해줍니다.

(1번 점이 뭐가 되었든 일단 그로부터 한 쪽 방향으로 점들을 정렬해야 가장 바깥쪽의 점부터 순서대로 확인해볼 수 있습니다.)

 

반시계 방향으로 점들을 정렬하는 원리는 CCW 알고리즘에 의한 것인데, 세 점 a, b, c가 있을 때 벡터 ab와 벡터 ac를 외적하여 양수가 나오면 세 점 a, b, c는 반시계 방향으로 위치함을 알 수 있습니다. (오른손 법칙 써보면 알 수 있음)

외적 공식은 애초에 외적이 그렇게 정의된 것이라서 그냥 공식에 좌표를 대입해주면 됩니다. (위의 코드에서 CCW 함수, 10~12행에 해당합니다.)

 

따라서 점 A와 B가 있을 때 OA x OB가 음수라면 둘을 swap하여 B가 A보다 먼저 오도록 정렬해주는 것입니다.

만약 OA x OB가 0이라면 그것은 O, A, B 세 점이 한 방향에 있는 것이고, 이 경우 y값이 더 작은 점이, y값 역시 같다면 x값이 더 작은 점이 먼저 오도록 정렬해줍니다.

 

이후 정렬된 점들이 있을 때 두 점만 스택에 넣어주고, 반복문에서 두 점을 빼서 임시로 저장한 뒤 다음 점을 가지고 와서 CCW > 0이면 아직 볼록이므로 다음 점으로 넘어가고, 그게 아니라면 마지막으로 넣어준 점을 빼고 다음 점을 가지고 와서 같은 검사를 거칩니다.

그러니까 예를 들어서 1번, 2번 점을 잡은 상태로 가장 바깥쪽에 있는 3번 점을 잡았는데 CCW 값이 음수로 나온다면 1번 점이 잘못 선택된 것입니다.

따라서 이 경우 while문을 한 번 더 돌아서 1번 점 역시 pop 되고 다른 점이 1번 점의 후보로 들어가게 됩니다. (이 점 역시 잘못 되었다면 더 이전 점을 선택하는 분기점으로 회귀하게 됨)

 

모든 점들에 대해 검사를 마치면 지금까지 스택에 들어있는 점들은 모두 볼록 다각형의 점들이므로 이 점들이 최종적으로 선택된 볼록 다각형의 꼭짓점들이 됩니다.

따라서 이 점들을 스택에서 빼서 사용해도 되고, 이 문제에서는 점들의 수만 출력하라고 하였으므로 스택의 사이즈만 출력해주면 됩니다.

 

 

 

참고로 제가 혹시나 해서 다른 블로그에 자신있게 풀이를 올리신 분들의 풀이도 채점해봤는데, 한 분 빼고 다 틀렸다고 나와서 개인적으로 재미있었습니다. (다른 사람들이 열심히 올린 코드 공부해서 풀었는데 똑같이 오답 나와버리면 당황할 것 같아서..)

보통 CCW compare 함수에서 대부분이 틀리셨는데, CCW가 0인 경우 return (a.x+a.y) < (b.x+b.y)로 정렬을 해버리면 오답을 받게 됩니다.