[Python] 1708번 볼록 껍질

https://www.acmicpc.net/problem/1708

1708번: 볼록 껍질

---

 

23/10/02

 

 

기하 알고리즘 중 대표적인 알고리즘, 볼록 껍질 알고리즘을 연습할 수 있는 좋은 문제이다.

 

이 문제를 통해 볼록 껍질을 구현하는 템플릿 코드를 구성하면 좋을 것이다. 

---

 

문제 접근 방식:

 

 

일반적으로 볼록 껍질을 구현하는 데에는 두 가지 방법이 존재한다.

 

이 문제의 해설에서는 두 가지 방법 모두 소개할 것이다.

 

첫번째 방법은 그라함 스캔이다.

 

그라함 스캔의 원리는 간단하지만, 파이썬에서의 구현은 그렇게 쉬운 편은 아니다.

 

점들이 있다면 먼저 점들을 각도 순으로 정렬하는 것이 첫번째 순서이다.

 

그러기 위해선 기준 점을 하나 잡아야 되는데, 그 기준점은 구현 상의 편의를 위해 일반적으로 가장 왼쪽 아래 점을 잡는다.

 

즉, $x$좌표가 가장 작으면서 동시에 $y$좌표가 가장 작은 점을 선택한다.

 

그렇게 되면 그 점을 일종의 "원점"으로 생각한다면 기준점을 제외한 모든 점이 제 1사분면에 놓이게 되는 것과 같은데, 이를 통해 단순히 그 점과 다른 점 사이의 직선의 기울기를 각도로 간주할 수 있어서 쉽게 각도 정렬을 할 수 있다.

 

각도 정렬을 할 때에는 기준점과 가까운 점을 우선으로 삼는다.

 

이후 정렬된 점 리스트에서 기준점과 그 다음 점을 스택에 넣고, CCW 알고리즘을 활용하여 다음과 같은 과정을 반복한다.

 

1. 스택의 가장 위의 두 점과 현재 넣고자 하는 점이 반시계방향을 이룬다면 현재 넣고자 하는 점을 넣는다.

2. 그렇지 않다면 스택의 가장 위의 점을 제거한다.

 

이 과정을 반복하면 스택에 있는 모든 점은 반시계 방향을 이루게 되는데, 이는 스택에 있는 모든 점으로 구성하는 다각형이 볼록함을 의미하고, 우리는 모든 점의 리스트를 탐색했으므로 모든 점을 포함하는 볼록 다각형을 구성함을 확인할 수 있다.

 

그라함 스캔의 시간 복잡도는 정렬이 요구되므로 $\mathcal{O}(N\mathrm{log}N)$의 시간 복잡도가 소요된다.

 

그라함 스캔을 구현할 때에 가장 유의할 점은 각도 정렬이다.

 

또한, 문제에서 볼록껍질을 이루는 직선 위에 3개의 점이 놓일 수 있냐 놓일 수 있지 않냐에 따라 CCW의 판정 결과에서 0을 포함하여 판정을 할 지, 0을 포함하지 않은 채로 판정을 할 지가 갈리게 된다.

 

그 점 또한 염두해두고 구현을 해야한다.

 

이 문제의 경우 볼록 껍질의 변에 점이 여러 개 있는 경우는 양 끝만 센다고 했으므로, 0을 포함하지 않은 채로 판정을 하는 것으로 구현해야 한다.

 

두번째 방법은 모노톤 체인이다.

 

모노톤 체인은 반절의 볼록껍질을 각각 구성하여 두 껍질을 합침으로써 하나의 볼록껍질을 완성하는 알고리즘이다.

 

가장 중요한 이점은 각도 정렬이 따로 필요하지 않아, 구현이 더욱 쉽다는 점이다.

 

스택에다 넣고 빼는 것은 그라함 스캔과 같으나, 각도 정렬이 되어있지 않기 때문에 절반의 껍질만 구성되어 나온다.

 

따라서 이를 CCW의 판정 값이 0보다 작을 때로 한번 더 진행하여, 나머지 절반의 껍질을 구성하고, 두 껍질을 합치는 작업을 진행하면 구현이 종료된다.

 

시간 복잡도는 $\mathcal{O}(N\mathrm{log}N)$의 시간 복잡도가 소요된다.

 

볼록 껍질에 대한 자세한 원리 이해는 다양한 블로그들이 있으니 참고해서 공부하면 도움이 될 것이다.

 

이 글에서는 따로 자세한 설명을 적지 않도록 할 것이다.

   

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 1708번 볼록 껍질
# 기하학, 볼록 껍질
import sys
input = sys.stdin.readline

def square_distance(point1, point2):
    return (point1[0]-point2[0])**2 + (point1[1]-point2[1])**2

def direction_vector(point1, point2): # 점 P1에서 P2로 가는 방향벡터 생성
    return (point2[0] - point1[0], point2[1] - point1[1])

def cross_product(vector_a, vector_b): # 평면 벡터 a와 평면 벡터 b를 외적한 값을 반환하는 함수
    return vector_a[0]*vector_b[1] - vector_a[1]*vector_b[0]

def CCW(P1, P2, P3): # P1->P2->P3 순으로 이었을 때 반시계방향이면 1, 시계방향이면 -1, 일직선이면 0
    vector_a = direction_vector(P1, P2)
    vector_b = direction_vector(P2, P3)
    k = cross_product(vector_a, vector_b)
    if k > 0:   # 양수면 반시계 방향
        return 1
    elif k < 0: # 음수면 시계 방향
        return -1
    else:       # 그 외의 경우는 일직선
        return 0

# 그라함 스캔으로 구현한 컨벡스헐
from math import atan2
def convex_hull_with_graham_scan(point_li):
    pivot = min(point_li, key = lambda point: (point[1], point[0]))
    point_li.remove(pivot)
    point_li.sort(key = lambda point:(atan2(point[1]-pivot[1], point[0]-pivot[0]), square_distance(pivot, point)))
    hull = [pivot]
    for point in point_li:
        while len(hull) > 1:
            if CCW(hull[-2], hull[-1], point) > 0:
                break
            hull.pop()
        hull.append(point)
    return hull

N = int(input())
point_li = list(tuple(map(int, input().rstrip().split())) for _ in range(N))
print(len(convex_hull_with_graham_scan(point_li)))

# 1708번 볼록 껍질
# 기하학, 볼록 껍질
import sys
input = sys.stdin.readline

def direction_vector(point1, point2): # 점 P1에서 P2로 가는 방향벡터 생성
    return (point2[0] - point1[0], point2[1] - point1[1])

def cross_product(vector_a, vector_b): # 평면 벡터 a와 평면 벡터 b를 외적한 값을 반환하는 함수
    return vector_a[0]*vector_b[1] - vector_a[1]*vector_b[0]

def CCW(P1, P2, P3): # P1->P2->P3 순으로 이었을 때 반시계방향이면 1, 시계방향이면 -1, 일직선이면 0
    vector_a = direction_vector(P1, P2)
    vector_b = direction_vector(P2, P3)
    k = cross_product(vector_a, vector_b)
    if k > 0:   # 양수면 반시계 방향
        return 1
    elif k < 0: # 음수면 시계 방향
        return -1
    else:       # 그 외의 경우는 일직선
        return 0

def convex_hull(point_li):
    point_li.sort()
    left_hull = [point_li[0], point_li[1]]
    right_hull = [point_li[0], point_li[1]]
    for i in range(2, len(point_li)):
        P3 = point_li[i]
        while len(left_hull) >= 2:
            P2 = left_hull.pop()
            P1 = left_hull[-1]
            if CCW(P1, P2, P3) > 0:
                left_hull.append(P2)
                break
        left_hull.append(P3)
        while len(right_hull) >= 2:
            P2 = right_hull.pop()
            P1 = right_hull[-1]
            if CCW(P1, P2, P3) < 0:
                right_hull.append(P2)
                break
        right_hull.append(P3)
        
    hull = left_hull + right_hull[len(right_hull)-2:0:-1]
    return hull

N = int(input())
point_li = list(tuple(map(int, input().rstrip().split())) for _ in range(N))
print(len(convex_hull(point_li)))