볼록 껍질(Convex Hull) 판별 문제란?
다각형의 외곽 점들이 시계 방향 순서로 주어져 있을 때, 이 점들이 볼록 껍질(convex hull)을 형성하는지 확인하는 문제입니다.
위 그림에서 알 수 있듯이, 볼록 껍질을 이루는 다각형은 연속된 세 점이 만드는 내부 각도가 항상 180° 이하라는 중요한 성질을 가집니다. 따라서 모든 연속된 세 점에 대해 각도를 검사했을 때 180°를 초과하는 경우가 하나라도 없다면, 해당 다각형은 볼록 껍질이라고 판단할 수 있습니다.
예를 들어 입력이 points = [(3,4), (4,7), (7,8), (11,6), (12,3), (10,1), (5,2)]라면 출력은 True가 됩니다.
문제 해결 접근 방식
다음 단계에 따라 문제를 해결할 수 있습니다.
- 점 목록의 길이를 n으로 설정합니다.
- i를 0부터 점 개수까지 반복하면서 다음 작업을 수행합니다.
- p1, p2, p3를 각각 points[i-2], points[i-1], points[i]로 지정합니다. 파이썬의 음수 인덱싱 덕분에 시작 지점에서 자동으로 마지막 점들로 순환(wrap-around)됩니다.
- 세 점 (p1, p2, p3)이 이루는 각도가 180°보다 크면 False를 반환합니다.
- 모든 검사를 통과하면 True를 반환합니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
import math
def get_angle(a, b, c):
angle = math.degrees(math.atan2(c[1]-b[1], c[0]-b[0]) - math.atan2(a[1]-b[1], a[0]-b[0]))
return angle + 360 if angle < 0 else angle
def solve(points):
n = len(points)
for i in range(len(points)):
p1 = points[i-2]
p2 = points[i-1]
p3 = points[i]
if get_angle(p1, p2, p3) > 180:
return False
return True
points = [(3,4), (4,7), (7,8), (11,6), (12,3), (10,1), (5,2)]
print(solve(points))입력
[(3,4), (4,7), (7,8), (11,6), (12,3), (10,1), (5,2)]
출력
True
코드 동작 원리
get_angle 함수는 점 a, b, c가 주어졌을 때 b를 꼭짓점으로 하는 두 벡터 ba와 bc 사이의 각도를 계산합니다. math.atan2를 사용해 각 벡터의 방위각을 구한 뒤 그 차이를 도(degree) 단위로 변환하고, 결과가 음수이면 360을 더해 0~360° 범위의 값으로 정규화합니다.
solve 함수는 시계 방향으로 배열된 점들을 순회하면서 연속된 세 점의 각도를 검사합니다. 각도가 180°를 초과하는 지점이 존재하면 오목한 부분이 있다는 의미이므로 False를 반환하고, 끝까지 통과하면 True를 반환합니다.
점의 개수를 n이라 할 때 각 점마다 상수 시간의 각도 계산만 수행하면 되므로, 전체 시간 복잡도는 O(n)으로 매우 효율적입니다.