백준 1708번: 볼록 껍질 (Convex hull)

문제링크: 1708번: 볼록 껍질 (acmicpc.net)

1708번: 볼록 껍질

이 문제는 N개의 점이 주어졌을 때 N개의 점을 모두 포함할 수 있는 볼록 껍질 (convex hull) 의 각 꼭지점들을 구하는 문제이다.  볼록 껍질이란 이 문제에서 설명하는 그대로 점들 중 일부 점들을 이용하여 볼록 다각형을 만드는데, 그 볼록 다각형이 모든 점을 포함할 수 있으면 볼록 껍질이 된다.

 

이 문제를 처음 봤을때 선분 교차 판정 때 이용한 벡터의 외적을 각 선분마다 사용하여 제일 바깥쪽의 꼭지점들을 구해 나가면 풀 수 있을 것이라는 생각이 들었지만 N이 100,000개로 매우 많기에 내가 생각한 방법은 무조건 안될 것 같았다. 도저히 풀 수 있는 생각이 나지 않아 인터넷을 찾아 시간 복잡도 O(NlogN)에 해결할 수 있는 그라함 스캔 알고리즘이 있다는 것을 알았다.

 

그라함 스캔 알고리즘은 일단 y축이 가장 낮은 좌표 중, 여러개라면 x축이 가장 적은 좌표를 base로 둔다. 그리고 각 점들을 base부터 각 점까지의 벡터 와 (1,0)벡터 사이의 각이 작은 순서대로 (base를 기준으로 반시계 방향으로) 배열한다. 그리고 배열의 순서대로 맨 앞부터 점을 stack자료구조를 사용해 다각형의 꼭지점 리스트에 조건 하에 추가하며 이어 가며 다각형을 만들어 간다.

 

만약 운 좋게 추가되는 모든 점들이 볼록 다각형을 만들 수 있다면 (기존의 마지막 선분) X (새로 추가되는 선문) 으로 외적하면 항상 양수 (반시계 방향)이어야 한다. 만약 외적값이 음수 (시계방향) 이라면 기존 선분과 새로 추가되는 선분의 내각이 180도 이상이라는 뜻이기 때문이다. 그러므로 만약 기존의 마지막 선분과 새로 추가되는 점으로 만드는 선분의 외적이 음수라면, 기존의 마지막 꼭지점을 stack에서 pop해 가며 외적값이 양수가 되는 꼭지점이 나올 때까지 반복한다. 위 과정을 배열의 끝까지 반복하면 stack에는 볼록 다각형의 꼭지점들이 남게 된다.

import sys
from functools import cmp_to_key

N=int(sys.stdin.readline().rstrip())

points=[]
for i in range(N):
    points.append(list(map(int,sys.stdin.readline().rstrip().split())))

points=sorted(points,key=lambda x:(x[1],x[0]))
base=points[0][:]
del points[0]

def cmpccw(a,b): #벡터 base-a, base-b의 외적, ccw:1 cw:-1 0이면 a가 짧으면:1, 길면: -1 반환
    v1=[a[0]-base[0],a[1]-base[1]]
    v2=[b[0]-base[0],b[1]-base[1]]
    if (v1[0]*v2[1])-(v1[1]*v2[0])>0:
        return 1
    elif (v1[0]*v2[1])-(v1[1]*v2[0])<0:
        return -1
    else:
        if (v1[0]**2+v1[1]**2)>(v2[0]**2+v2[1]**2):
            return -1
        else:
            return 1

def ccw(a,b,c,d): #벡터 a-b, c-d의 외적 ccw:1 cw:-1 line:0
    v1=[b[0]-a[0],b[1]-a[1]]
    v2=[d[0]-c[0],d[1]-c[1]]
    if (v1[0]*v2[1])-(v1[1]*v2[0])>0:
        return 1
    elif (v1[0]*v2[1])-(v1[1]*v2[0])<0:
        return -1
    else:
        return 0

points=sorted(points,key=cmp_to_key(cmpccw),reverse=True)

ans=[]
ans.append(base)
ans.append(points[0])
for i in range(1,N-1):
    new=points[i]
    if ccw(ans[-2],ans[-1],ans[-1],new)==1:
        ans.append(new)
        
    elif ccw(ans[-2],ans[-1],ans[-1],new)==-1:
        ans.pop()
        while ccw(ans[-2],ans[-1],ans[-1],new)<=0:
            ans.pop()
        ans.append(new)
        
    elif ccw(ans[-2],ans[-1],ans[-1],new)==0:
        ans.pop()
        ans.append(new)

print(len(ans))

실제로 우리가 N-1개의 점에 대해 base부터 점까지의 벡터와 (1,0) 벡터의 각을 구하는 방법은 삼각함수를 이용해야 하므로 소수점의 오차가 있을 수 있고 시간도 오래 걸리므로 각 벡터끼리의 외적을 비교해 가며 points들을 sort한다. 먼저 각 점을 비교해야 하므로 점 a,b를 비교한다 할때 사용할 cmpccw(a,b)함수를 만들었다.

 

cmpccw(a,b)함수는 (base->a)X(base->b) 벡터의 외적이 양수면 ccw이므로 1, 음수면 cw이므로 -1으로 반환한다. 만약 같다면 base에 가까운 점의 우선순위가 높아져야 하므로 a가 짧으면 1, 길면 -1을 반환한다. 만약 ccw이라면 b의 각도가 a보다 큰 것이므로, a의 우선순위가 높다. ccw때 1을 반환했으므로, 같은 원리로 a가 짧으면 우선순위가 높은 경우로 1을 반환해야 한다.

 

이제 여기서 points들을 sort하는 과정을 O(NlogN)내에 해야 하는데 저번에 구현한 세그먼트 트리를 이용한 merge sort를 진행하여 비교할때 리스트의 값을 비교하는 것이 아닌 각 points를 cmpccw()를 통해 우선순위가 높은 것을 앞으로 빼 가며 하려고 했다. 그렇지만 파이썬의 내장 함수의 sort의 key를 어떻게 잘 사용하면 방법이 있지 않을까 찾아보다가 파이썬의 functools의 cmp_to_key함수를 사용하면 비교 함수를 파이썬이 sort할 수 있는 key로 바꾸어 주는 함수가 있어서 그걸 사용했다. 특이사항으로 cmp함수는 cmpccw(a,b)처럼 입력값이 비교하는 2개어야 하고, 만약 a<b 는 음수, a==b는 0, a>b는 양수를 반환해야 한다. 그래서 일부러 cmpccw()함수와 보편적인 ccw()함수 두개를 만들었다. 아까 우리는 a가 우선순위일때 1을 주기로 해서 우선순위인 점이 가장 큰것으로 판단하여 맨 뒤에 있을 것이다. reverse=True 해준다.

 

cmp_to_key 참조는 정렬 HOW TO — Python 3.11.1 문서

Sorting HOW TO

 

그렇게 해서 배열된 points중 가장 첫번째 points는 무조건 볼록 껍질에 포함되므로 ans에 추가시켜 주고 1부터 N-1까지 points[idx]에 대해 그라함 스캔 알고리즘을 진행한다. 만약 ccw가 1이라면 new를 추가 해주고, -1이라면 위에 설명한 것처럼 직전의 벡터와의 외적이 양수가 될때까지 pop해준다. 만약 ccw가 0이라면 두개는 같은 직선 위에 있는 것이다. 그러므로 직전의 꼭지점은 꼭지점이 아니라 변 중앙의 있는 점이므로 pop해주고 new를 추가 해 준다.

 

밑은 직접 구현한 merge sort 합병정렬을 이용한 방법이다. 원래대로 풀었을 시 1140ms 정도였는데 744ms로 더 빨라졌다. 볼록 껍질 알고리즘 뿐만아니라 비교를 통해 O(NlogN)으로 정렬하는 법을 배울 수 있어 좋은 문제였다.

import sys
from functools import cmp_to_key

N=int(sys.stdin.readline().rstrip())

points=[]
for i in range(N):
    points.append(list(map(int,sys.stdin.readline().rstrip().split())))

points=sorted(points,key=lambda x:(x[1],x[0]))
base=points[0][:]
    
del points[0]

def cmpccw(a,b): #벡터 base-a, base-b의 외적, ccw:1 cw:-1 0이면 a가 짧으면:1, 길면: -1 반환
    v1=[a[0]-base[0],a[1]-base[1]]
    v2=[b[0]-base[0],b[1]-base[1]]
    if (v1[0]*v2[1])-(v1[1]*v2[0])>0:
        return 1
    elif (v1[0]*v2[1])-(v1[1]*v2[0])<0:
        return -1
    else:
        if (v1[0]**2+v1[1]**2)>(v2[0]**2+v2[1]**2):
            return -1
        else:
            return 1

def ccw(a,b,c,d): #벡터 a-b, c-d의 외적 ccw:1 cw:-1 line:0
    v1=[b[0]-a[0],b[1]-a[1]]
    v2=[d[0]-c[0],d[1]-c[1]]
    if (v1[0]*v2[1])-(v1[1]*v2[0])>0:
        return 1
    elif (v1[0]*v2[1])-(v1[1]*v2[0])<0:
        return -1
    else:
        return 0

def merge_sort(start,end,index):
    if start==end:
        lst=[points[start]]
        return lst
    mid=(start+end)//2
    leftsort=merge_sort(start,mid,2*index)
    rightsort=merge_sort(mid+1,end,2*index+1)
    sortlst=merge(leftsort,rightsort)    
    return sortlst

def merge(left,right):
    i=0
    j=0
    sortlst=[]
    while i<len(left) and j<len(right):
        if cmpccw(left[i],right[j])==1:
            sortlst.append(left[i])
            i+=1
        elif cmpccw(left[i],right[j])==-1:
            sortlst.append(right[j])
            j+=1
    if i==len(left):
        for b in right[j:]:
            sortlst.append(b)
    elif j==len(right):
        for a in left[i:]:
            sortlst.append(a)
    return sortlst

points=merge_sort(0,N-2,1)

ans=[]
ans.append(base)
ans.append(points[0])
for i in range(1,N-1):
    new=points[i]
    if ccw(ans[-2],ans[-1],ans[-1],new)==1:
        ans.append(new)
        
    elif ccw(ans[-2],ans[-1],ans[-1],new)==-1:
        ans.pop()
        while ccw(ans[-2],ans[-1],ans[-1],new)<=0:
            ans.pop()
        ans.append(new)
        
    elif ccw(ans[-2],ans[-1],ans[-1],new)==0:
        ans.pop()
        ans.append(new)

print(len(ans))