[Python] 백준 1708 - 볼록 껍질

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

 

문제

다각형의 임의의 두 꼭짓점을 연결하는 선분이 항상 다각형 내부에 존재하는 다각형을 볼록 다각형이라고 한다. 아래 그림에서 (a)는 볼록 다각형이며, (b)는 볼록 다각형이 아니다.

조금만 생각해 보면 다각형의 모든 내각이 180도 이하일 때 볼록 다각형이 된다는 것을 알 수 있다. 편의상 이 문제에서는 180도 미만인 경우만을 볼록 다각형으로 한정하도록 한다.

2차원 평면에 N개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 볼록 다각형을 만드는데, 나머지 모든 점을 내부에 포함하도록 할 수 있다. 이를 볼록 껍질 (CONVEX HULL) 이라 한다. 아래 그림은 N=10인 경우의 한 예이다.

점의 집합이 주어졌을 때, 볼록 껍질을 이루는 점의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범위는 절댓값 40,000을 넘지 않는다. 입력으로 주어지는 다각형의 모든 점이 일직선을 이루는 경우는 없다.

출력

첫째 줄에 볼록 껍질을 이루는 점의 개수를 출력한다.

볼록 껍질의 변에 점이 여러 개 있는 경우에는 가장 양 끝 점만 개수에 포함한다.

 

---

 

풀이

오늘은 매우매우 기초적이고 유명한 문제인 컨벡스 헐 문제를 <알고리즘 트레이닝: 프로그래밍 대회 입문 가이드(2판) - 안티 라크로넨>(2019) 을 참고해서 앤드류 알고리즘으로 풀어볼 것이다.

 

다른 블로그들이나 풀이들을 보면 대부분 그래햄 스캔 알고리즘으로 푼 것들이 많다.

 

그런데 이 책에는 그래햄 스캔 대신 앤드류 알고리즘이 소개되어 있었다.

 

GPT한테 물어보니 앤드류 알고리즘이 더 깔끔하고 단순하고 하다길래.... 직접 이걸 구현해보기로 했다.

---

앤드류 알고리즘은 어떻게 동작하는가?

 

앤드류 알고리즘은 위쪽 껍질과 아래쪽 껍질을 따로 구해서 합치는 방법을 이용한다.

그러기 위해서 일단 x좌표 기준으로, 2순위로는 y좌표 기준으로 점들을 정렬한다.

 

위쪽 껍질와 아래쪽 껍질을 구하는 방법은 매우 유사하므로 위쪽 껍질의 경우에 대해서만 살펴보겠다.

 

 

그런 다음, 각 점들을 리스트에 추가해가면서 다음을 반복한다.

 

1. 가장 마지막 3개의 점을 가지고 CCW를 해보았을 때 반시계 방향이거나 일직선이면 시계방향이 될 때까지 마지막에서 두 번째 점을 삭제한다.

 

2. 껍질 리스트에 점을 추가한다.

---

 

 

1번을 보면 굵은색 글씨로 시계방향이 될 때까지라고 나와있다. 이게 핵심이다. 분명 책에도 저렇게 나와있었다. 그런데 멍청한 나는 이걸 못 보고 그냥 1번만 삭제했다.

 

그랬더니 당연히 WA가 뜨지.

 

멍청한 나는 그걸 또 모르고 '혹시 모르니까 한 번 더 체크해줘야지' 하면서 불필요하게 CCW를 한 번 더 써서 아래와 같은 코드를 만들었다.

 

def CCW(d1, d2, d3): #d1, d2, d3은 튜플임
    x1, y1 = d1
    x2, y2 = d2
    x3, y3 = d3
    tmp = (x2-x1)*(y3-y2) - (x3-x2)*(y2-y1)
    if tmp > 0: return 1
    elif tmp < 0: return -1
    else: return 0

N = int(input())
dots = []
for i in range(N):
    x, y = map(int, input().split())
    dots.append((x, y))

ans = 0

#Top Hull
dots.sort()

hull = [dots[0], dots[1]]
idx = 2
while True:
    hull.append(dots[idx])
    if CCW(hull[-3], hull[-2], hull[-1]) >= 0:  # 반대 방향일떄?
        tmp = hull.pop()
        hull.pop()
        hull.append(tmp)

    if len(hull) >= 3:
        if CCW(hull[-3], hull[-2], hull[-1]) >= 0:  # 반대 방향일떄?
            tmp = hull.pop()
            hull.pop()
            hull.append(tmp)

    idx += 1
    if idx >= N:
        break

ans += len(hull)

#Bottom Hull
dots = dots[::-1]

hull = [dots[0], dots[1]]
idx = 2
while True:
    hull.append(dots[idx])
    if CCW(hull[-3], hull[-2], hull[-1]) >= 0: #반대 방향일떄?
        tmp = hull.pop()
        hull.pop()
        hull.append(tmp)

    if len(hull) >= 3:
        if CCW(hull[-3], hull[-2], hull[-1]) >= 0: #반대 방향일떄?
            tmp = hull.pop()
            hull.pop()
            hull.append(tmp)

    idx += 1
    if idx >= N:
        break

ans += len(hull)
print(ans-2)

 

위 코드는 틀린 코드이다.

굵은 글씨로  시계방향이 될 때까지 라고 강조되어있는 이유에 대한 반례가 있다.

다음과 같은 반례를 보자(게시판에 질문했는데 착하신 분께서 도와주심ㅠㅠ감사합니다 잠 못 잘 뻔 했어요).

 

7
0 0
1 1
2 1
3 0
4 10
5 9
6 0

 

위 테스트케이스에서 내 처음 코드로 위쪽 껍질을 구하면 이렇게 된다. CCW 검사를 최대 2번밖에 안해주었기 때문이다!!! 볼록하게 될 때까지 계속 해줘야하는데ㅠㅠ

 

효율적으로 반복문을 제대로 짜보면 정답 코드는 아래와 같이 짤 수 있다.

 

정답 코드

def CCW(d1, d2, d3): #d1, d2, d3은 튜플임
    x1, y1 = d1
    x2, y2 = d2
    x3, y3 = d3
    return (x2-x1)*(y3-y2) - (x3-x2)*(y2-y1)

N = int(input())
dots = []
for i in range(N):
    x, y = map(int, input().split())
    dots.append((x, y))

ans = 0

#Top Hull
dots.sort()

hull = []
for d in dots:
    while len(hull) >= 2 and CCW(hull[-2], hull[-1], d) >= 0:
        hull.pop()
    hull.append(d)
ans += len(hull)

#Bottom Hull
dots = dots[::-1]

hull = []
for d in dots:
    while len(hull) >= 2 and CCW(hull[-2], hull[-1], d) >= 0:
        hull.pop()
    hull.append(d)
ans += len(hull)
print(ans-2)

 

오늘 앤드류 알고리즘이라는 새로운 컨벡스헐 제작방법을 배웠다. 참으로 유익한 경험이었다.