문제 링크: https://www.acmicpc.net/problem/1708

주어진 점들을 모두 포함하는 볼록 껍질(Convex Hull)을 구하는 문제입니다.

풀이

볼록 껍질(Convex Hull)

볼록 껍질이란, 주어진 점들을 모두 포함하는 가장 작은 볼록 다각형(또는 집합)을 말합니다. 이번 문제에서는 2차원 평면 상에 주어진 점들을 모두 포함하는 볼록 다각형을 말합니다.

여기서, 볼록 다각형이란 "다각형의 임의의 두 꼭짓점을 연결하는 선분이 항상 다각형 내부에 존재하는 다각형을 말합니다. 문제의 예시로 보면, (a)는 볼록 다각형이지만 (b)는 아님을 알 수 있습니다.

볼록 껍질 구하기

​2차원 평면 상에 주어진 $N$개의 점들을 모두 포함하는 볼록 껍질은 다음의 과정으로 구할 수 있습니다.

1. 주어진 점들을 정렬해 시작점을 잡습니다.
   1. 점들 중 y좌표가 가장 작은 점으로, 만약 같다면 그 중 x좌표가 가장 작은 점으로 시작 점을 정합니다.
2. 이후, 시작점을 기준으로 점들을 반시계 방향으로 정렬합니다.
   1. 이 과정은 CCW를 사용해 진행됩니다.
3. 정렬된 점들을 기준에 따라 스택에 넣거나 빼며 볼록 다각형을 구성하는 점들을 찾습니다.
   1. 처음 2개의 점을 스택에 넣습니다.
   2. 이후 세 번째 점부터 마지막 점까지 반복하며 다음을 반복합니다:
      1. 스택의 위에서부터 2개의 점 (가장 최근에 넣은 2개의 점)과 현재의 점으로 CCW를 통해 세 점의 방향 관계를 구합니다.
      2. 현재 점이 기존 2개의 점의 왼쪽에 위치한다면 (세 점이 반시계 방향으로 연결되었다면) 점을 스택에 추가합니다.
         그렇지 않은 경우, 스택을 1번 pop하고 다시 비교합니다.

1) 좌표 순 정렬하기

먼저, 입력으로 받은 점들을 좌표 순으로 정렬합니다. 이번 정렬은 다음 정렬의 기준으로 사용할 점을 찾기 위해 진행하는 과정입니다.

이번 코드에서는 Python3의 내장 모듈인 functools에서 제공하는 cmp_to_key함수를 사용했습니다.

현재 Python 3의 sorted 및 list.sort 함수는 key라는 이름의 키워드 인자로 정렬 기준을 정의할 수 있습니다. 이때, key는 인자를 1개만 갖는 함수를 받아서, 필요한 정렬 기준을 정의하기에 부족할 수 있습니다.
C/C++의 경우 인자를 2개 받는 비교 함수 cmp를 정렬 함수의 인자로 전달해 원하는 비교 방식으로 정렬할 수 있는데, Python 3에서는 안되는 걸까요?

이런 경우에 사용하는 것이 cmp_to_key 함수입니다. 이 함수는 인자를 2개 받는 비교 함수를 sorted와 list.sort의 key 인자로 사용할 수 있게 변환해줍니다. 이때 사용되는 비교 함수는 두 인자의 비교 결과를 양수/0/음수로 반환해야 합니다.

• 음수: 기존 list에서 두 원소의 위치를 바꿔야 하는 경우
• 0: 두 원소의 값이 같은 경우 (양수일때와 같이 원소의 위치를 바꾸지 않습니다.)
• 양수: 기존 list에서 두 원소의 위치를 바꾸지 않아야 하는 경우

두 점의 좌표를 받아, 두 점의 y좌표를 비교하는 함수 cmp_coord를 정의했습니다. 만약 두 점의 y좌표가 같다면 x좌표에 따라 비교합니다.

from functools import cmp_to_key

# 1. 좌표 순으로 정렬하기

def cmp_coord(p1, p2):
    if p1[1] == p2[1]:
        return p1[0] - p2[0]
    return p1[1] - p2[1]

points = sorted(
  (tuple(map(int, input().split())) for _ in range(N)), 
  key=cmp_to_key(cmp_coord)
)

2) 시작점으로부터 반시계 방향으로 정렬하기

앞서 좌표 순으로 점들을 정렬했으므로, points 배열의 0번 원소는 전체 점들 중에서 y좌표가 제일 작은 점들 중에서 x좌표도 제일 작은 점이 됩니다. 이 점을 기준으로 다른 점들을 반시계 방향으로 정렬해줘야 합니다.

세 점의 방향 관계는 CCW를 사용해 구할 수 있습니다. ccw 함수는 CCW의 판별식을 계산하는 함수입니다. dist함수는 두 점 사이의 거리의 제곱을 계산합니다.

cmp_ccw함수는 cmp_to_key에 사용할 2개 인자를 받는 비교 함수입니다. 이 함수에서는 기준점인 points[0]과 비교에 사용되는 2개의 점을 통해 CCW의 판별식을 계산하고, 그 값을 통해 정렬 여부를 판단합니다.

• CCW < 0: 이미 반시계 방향이므로 위치 변경 X
• CCW > 0: 시계 방향이므로 두 원소의 위치를 바꿔야 함
• CCW = 0: 두 점이 일직선 상에 위치하므로, 기준점에 더 가까운 점을 더 앞에 위치하도록 한다.

# 2. 좌표를 기준점으로부터 반시계 방향으로 정렬하기

def ccw(p1, p2, p3):
    return (p1[0] * p2[1] + p2[0] * p3[1] + p3[0] * p1[1]) - (p1[1] * p2[0] + p2[1] * p3[0] + p3[1] * p1[0])

def dist(p1, p2):
    return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2

def cmp_ccw(p1, p2):
    c = ccw(points[0], p1, p2)
    if c == 0:
        return dist(points[0], p1) - dist(points[0], p2)
    return -c

points = sorted(points, key=cmp_to_key(cmp_ccw))

3) 볼록 껍질 구하기

이제, 반시계 방향으로 정렬한 점들을 사용해 볼록 껍질을 찾아야 합니다.

1. 처음 2개의 점을 스택에 넣습니다.
2. 이후 세 번째 점부터 마지막 점까지 반복하며 다음을 반복합니다:
   1. 스택의 위에서부터 2개의 점 (가장 최근에 넣은 2개의 점)과 현재의 점으로 CCW를 통해 세 점의 방향 관계를 구합니다.
   2. 현재 점이 기존 2개의 점의 왼쪽에 위치한다면 (세 점이 반시계 방향으로 연결되었다면) 점을 스택에 추가합니다.
      그렇지 않은 경우, 스택을 1번 pop하고 다시 비교합니다.

from collections import deque

# 3. 볼록 껍질 구하기
stack = deque([points[0], points[1]])
for i in range(2, N):
    while len(stack) >= 2:
        b = stack.pop()
        a = stack[-1]
        if ccw(points[i], a, b) > 0:
            stack.append(b)
            break
    stack.append(points[i])

print(len(stack))

7개의 점에 대해 볼록 껍질을 구하는 과정을 그림으로 보면 다음과 같습니다.

이미지 출처: 컨벡스 헐(Convex Hull) 알고리즘 (david0506)
https://david0506.tistory.com/62

전체 코드

from functools import cmp_to_key
from collections import deque
input = open(0).readline

N = int(input())

# 1. 좌표 순으로 정렬하기

def cmp_coord(p1, p2):
    if p1[1] == p2[1]:
        return p1[0] - p2[0]
    return p1[1] - p2[1]

points = sorted(
  (tuple(map(int, input().split())) for _ in range(N)), 
  key=cmp_to_key(cmp_coord)
)

# 2. 좌표를 기준점으로부터 반시계 방향으로 정렬하기

def ccw(p1, p2, p3):
    return (p1[0] * p2[1] + p2[0] * p3[1] + p3[0] * p1[1]) - (p1[1] * p2[0] + p2[1] * p3[0] + p3[1] * p1[0])

def dist(p1, p2):
    return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2

def cmp_ccw(p1, p2):
    c = ccw(points[0], p1, p2)
    if c == 0:
        return dist(points[0], p1) - dist(points[0], p2)
    return -c

points = sorted(points, key=cmp_to_key(cmp_ccw))

# 3. 볼록 껍질 구하기
stack = deque([points[0], points[1]])
for i in range(2, N):
    while len(stack) >= 2:
        b = stack.pop()
        a = stack[-1]
        if ccw(points[i], a, b) > 0:
            stack.append(b)
            break
    stack.append(points[i])

print(len(stack))