BOJ 1708 볼록 껍질

 

처음 문제를 봤을 땐 '이게 뭐지?' 싶었다. 그러다가 문득 깨달았다. '이게 그 유명한 Convex Hull 문제구나!!' 

예전에 고등학교에 다니다가 컨벡스 헐에 대한 정보를 얼핏 들은적이 있었다. 그래서 이 문제에 관해서 어느정도 알고있었다. 

그래서 약간의 기대감과 함께 문제에 손을 대기 시작했다.

 

하지만 처음엔 막막했다. 도저히 어디서부터 손을 대야하는지 모르겠다. 일단 내가 생각한 아이디어는 큰 원을 만들어서 이를 내접시키는 방식으로 진행해보고자 했다. 

하지만 이 방식은 너무 어렵다. 그래서 다른 방법을 생각해보려 했으나 마땅치 않아 결국 구글을 켜게 되었다.

 

그렇게 찾은 결과는, Graham Scan 알고리즘이었다. 정확히 컨벡스 헐을 노리고 만든 알고리즘이었다. 이 알고리즘의 과정은 그리 어렵진 않았다.

0. 모든 점들을 특정 점을 기준으로 시계 또는 반시계방향으로 정렬한다. 그리고 시작점과 그 다음점을 스택에 넣는다.

1. 스택에 들어있는 마지막에서 2번째 점, 1번째 점을 기준으로 현재 점이 오른쪽에 있는지 왼쪽에 있는지 판단한다.

2. 만약 오른쪽에 있으면 스택에서 마지막 점을 pop시킨다. 왼쪽이라면 현재 점을 스택에 추가한다. 그리고 다시 1을 반복해서 왼쪽에 있는 점이 나올 때까지 반복한다.

3. 이를 모든 점에서 실행해서 결과적으로 스택의 길이를 출력한다.

일단 여기서 문제점이 2가지가 있었다.

첫 번째, 어떻게 반시계 방향으로 점들을 정렬시킬 것인가.

두 번째, 왼쪽인지 오른쪽인지 어떻게 판단할 것인가.

 

첫 번째 문제점은 그나마 간단했다. 애초에 시작점을 정해두고 시작하는 것이고 시작점을 기준으로 반시계 방향으로 정렬하는 것이기에 시작점으로 부터 x+방향으로 뻗은 반직선을 360도 돌려서 스캔하는 방식으로 정렬하면 될거같았다. 

대충 이런 느낌으로 반직선 자체를 회전시켜서 그 때의 Theta값을 얻는 느낌이다. 이를 얻기 위해서 점의 좌표와 시작점의 좌표에 기반해 arctan(x/y)를 시켜 Theta를 구하는 방식으로 진행했다.

 

하지만 진짜 문제는 어떻게 왼쪽과 오른쪽을 구분할것인지 였다. 

내가 생각한 방법은 실제로 시작점에서 특정 점을 지나는 직선의 방정식을 구해서 이를 기준으로 구분하고자 했다. 

하지만 여기엔 몇 가지 문제가 있었다. 

첫 번째 문제는 두 점이 나타내는 벡터의 사분면에 따라서 검사해야 할 조건이 달라진다는 것이었고

두 번째 문제는 거의 모든 점에 대해서 전부 검사를 진행해야 하기 때문에 사실상 시간복잡도가 O(N**2)가 된다는 것이었다,,

그래서 이 방식은 포기하고 다른 방법을 찾기로 했다

 

그렇게 다른 방법을 찾은 결과, 벡터의 외적을 통해서 어디에 위치해 있는지부터 일직선상에 위치해있는지 까지 모두 구할 수 있다는 사실을 알게됐다. 

 

벡터의 외적? 고2 기하 시간에 잠깐 스치듯이 듣고 한번도 들어본 적 없는 단어였다. 그래서 다시 공부를 하기 시작했다. 

벡터의 외적은 한 벡터에 대해 다른 벡터가 이루는 평행사변형의 넓이를 의미하는 듯 했다. 

근데 특이한 점이 이 넓이가 음수가 될 수 있단 점이었다. 한 벡터에 대해서 다른 벡터가 왼쪽에 위치하냐, 오른쪽에 위치하냐에 따라 부호가 달라진다는 것이었다. 이를 통해 문제를 풀면 될 듯 했다.

 

코드를 짜는 것은 순조로웠다. 코드를 짜기에 어려운 개념은 많지 않았기에 빠르게 짜고 제출을 한 순간, 틀려버렸다. 나는 스택 계산에 문제가 있나 싶어 몇시간동안 계속 스택만 쳐다보다가 결국 잠시 쉬기로 했다. 그렇게 쉬고 온 뒤 코드를 완전히 갈아엎고 더 효율적이고 컴팩트한 코드로 다시 짰다. 하지만 이렇게 다시 짠 코드 조차도 틀려버리자 나는 우리 동아리 선배님들에게 도움의 손길을 요청했다. 이 알고리즘에서 한 가지 내가 간과한 점이 있었다. 바로 Theta가 같은 상황을 제외했던 것이다. Theta가 같으면 거리가 가깝든 멀든 무작위로 배열이 된다. 나는 가깝든 멀든 어떻게든 되겠지라고 대충 넘겼었는데 이는 엄청난 오산이었다. 

사실 생각해보면 당연한건데 더 먼곳을 먼저 탐색한다면 짧은 거리에 있는 점이 제대로 검사되지 않고 지나갈 가능성이 있다. 이 때문에 답이 다르게 나올 수 있단 것을 깨달았다. ( 도움을 주신 저희 동아리 선배님,, 감사드립니다 )

그래서 마지막으로 만약 각이 같은 경우 거리에 따라서 정렬이 되도록 알고리즘을 수정한 뒤 정답을 맞을 수 있었다.

 

 

그리고 나중에 안 사실인데 이렇게 atan으로 구하게 되면 실수의 부동소수점 계산이 틀어질 수도 있기 때문에 이런 방식보다는 외적을 이용한 정렬을 하는것이 낫다는 것을 알았다. 생각해보면 당연한 이야기다. 실수를 통해 비교 연산을 하다 보면 언젠간 틀어지는 것이 당연지사, 따라서 이러한 실수에 영향을 받지 않는 방법으로 정렬하는 것은 당연한 것이었다.

다음에 Convex Hull 문제를 접하게 되면 그땐 ccw를 이용한 정렬로 한번 더 도전해보려 한다. 

 

from math import atan2

N = int(input())
points = []
minx,miny = float('inf'), float('inf')

for _ in range(N):
    x,y = map(int,input().split())
    if y < miny: 
        minx,miny = x,y
    elif y == miny: minx = min(minx,x)
    points.append([x,y,0])

def getTheta(center):
    cx,cy = center
    for i in range(N):
        x,y,_ = points[i]
        if center != (x,y):
            points[i][2] = atan2(y-cy,x-cx)

getTheta((minx,miny))
points.sort(key=lambda x: (x[2], (x[0] - minx)**2 + (x[1] - miny)**2))
points = [(x,y) for x,y,_ in points]

def CCW(p1, p2, p3):
    vec1 = (p2[0] - p1[0], p2[1] - p1[1])
    vec2 = (p3[0] - p1[0], p3[1] - p1[1])
    return vec1[0] * vec2[1] - vec1[1] * vec2[0]

def Run():
    stack = [points[0], points[1]]
    for i in range(2, N):
        while len(stack) >= 2 and CCW(stack[-2], stack[-1], points[i]) <= 0:
            stack.pop()
        stack.append(points[i])
    return len(stack)

print(Run())