볼록껍질

김태성·2024년 6월 15일
0

알고리즘

목록 보기
18/30
post-thumbnail

드디어 시간이 나서 알고리즘 공부를 할 수 있게 되었다.
정말 바쁜 1주일이었고.. 이번 주말은 느긋하게 보낼 생각이다...

그리고 풀고 싶었던 알고리즘이 있었는데, 처음배우는거라 이해는 되어도 코드로 나오지가 않기에 정답 코드를 보며 왜 이렇게 코드를 짰는지 분석해보자..

쓰레기 슈트 다국어

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 128 MB 3809 894 622 21.794%
문제
선영이는 쓰레기를 편하게 버리기 위해서 빌딩에 쓰레기 슈트를 만들었다. 쓰레기 슈트는 빌딩에 설치할 수 있는 속이 빈 튜브다. 튜브로 쓰레기를 떨어뜨리면, 쓰레기는 지하실까지 떨어지게 된다.

쓰레기 슈트를 만드는 일은 매우 어려운 일이다. 사람들이 무엇을 버릴지 알 수 없기 때문에, 쓰레기 슈트에 들어가지 않는 쓰레기를 버린다면, 슈트가 막혀버릴 수 있기 때문이다. 쓰레기 슈트를 만드는데 드는 비용은 그 크기에 비례한다. 따라서, 최대한 작게 만드는 것이 효율적이다.

먼저, 쓰레기 슈트를 만드는 문제를 2차원으로 단순화 시켜보자. 슈트는 일정한 너비를 가지고 있고, 다각형으로 모델링된 물체를 이 곳의 상단에 넣을 수 있다.

물체를 넣기 전에, 슈트에 들어갈 수 있게 돌려야 할 수도 있다. 슈트에 던진 이후에는 일직선으로 아래로 떨어지고, 그 동안 물체는 회전하지 않는다.

아래 그림은 물체를 쓰레기 슈트에 들어갈 수 있게 회전시킨 다음 버리는 그림이다.

어떤 물체가 주어진다. 이 물체가 통과할 수 있는 가장 작은 슈트의 너비를 구하는 프로그램을 작성하시오.

입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 물체(다각형)의 꼭짓점의 개수 n이 주어진다. (3 ≤ n ≤ 100)

다음 n개 줄에는 꼭짓점의 좌표 xi와 yi가 주어진다. (0 ≤ xi, yi ≤ 104) 꼭짓점은 다각형을 이루는 순서대로 주어진다.

입력으로 주어지는 다각형의 좌표는 모두 서로 다르며, 다각형의 변은 교차하지 않는다. 엄밀히 따지면, 인접한 변은 한 꼭짓점을 공유한다는 예외가 하나 있다. 물론, 이 경우는 교차하는 것으로 생각하지 않는다.

마지막 테스트 케이스의 다음 줄에는 0이 하나 주어진다.

출력
각 테스트 케이스마다 케이스 번호와 가장 작은 쓰레기 슈트의 너비를 출력한다. 너비는 가장 가까운 0.01의 배수로 올림하여 소수점 둘째 자리까지 출력한다.

볼록껍질 이라는 알고리즘이다.
이전에 풀었던 CCW를 응용한 문제이다.
링크 : https://velog.io/@kts5927/CCW
간단하게 말하면

  • 2차원 평면상에 흩뿌려진 점들 중, 최소한의 직선을 가지고 최외곽의 점들을 이어라

이다.
CCW도 그냥 외적해서 양수면 반시계, 음수면 시계 방향이라는 것이다.

그러니까, 이번에도 그저 CCW를 통해 특정한 점들을 list에 집어넣고, pop, push를 하며 연결되는 직선이 시계방향/반시계방향으로 꺾이는지 판단하는 문제이다.

말이 길어지고 복잡하니 그림으로 보자.

위와 같은 점들이 2차원 평면상에 흩어져 있다고 보자. 여기서 우리는 어떻게 하면 최외곽 점들만을 연결할 수 있을까?

일단 하나 이어봤다.
그럼 우리는 CCW를 알고 있으니 다른 한 점을 더 잇게되면, CCW를 통해 시계/반시계 판별을 할 수가 있다.

이렇게 이었다고 생각해보자.
CCW의 값이 음수가 되었으니(시계방향) 우리는 이것이 잘못된 값이라는걸 알 수 있다.
그럼 우리는 이 점들을 pop 해서 CCW의 음수값이 나온 직선들을 없애줄 것이다.


이번에는 다른 점을 잡아보았다.
이 점에서 출발하는 모든 직선들은 CCW가 양수이기 때문에(반시계)
어디든 이을수 있다.

위의 방식대로 계산을 쭉 진행하다 보면 최외곽 점들을 이을 수 있게 된다. 하지만 여기서 중요한 것이 있는데,

이렇게 연결되어도 어쨌든 반시계방향으로 다각형이 만들어졌으니 성립이 되는 것이다. 그러니 우리는
점을 이었을때 CCW가 음수가 되는 기준으로 정렬해야 한다.

이는 뒤의 코드 설명에 나오게 된다.
정답코드 출처 : https://magentino.tistory.com/461

from functools import cmp_to_key
import sys
import math

MAX = float('inf')

def ccw(a,b,c) :
    return (a[0]*b[1] + b[0]*c[1] + c[0]*a[1] ) - (a[1]*b[0] + b[1]*c[0] + c[1]*a[0])

def cmp(a,b) :
    if ccw(ref,a,b) < 0:
        return 1
    else:
        return -1
    
def convex_hull(points) :
    stk = points[:2]
    for point in points[2:] :
        while len(stk) > 1 and ccw(stk[-2] , stk[-1], point) < 0:
            stk.pop()
        stk.append(point)
    return stk
    
def distance(target, p0, p1) :
  if p0[0] == p1[0] :
    return abs(target[0] - p0[0])
  if p0[1] == p1[1] :
    return abs(target[1] - p0[1])
  a, b = (p1[1] - p0[1]) / (p1[0] - p0[0]), -1
  c = -a * p0[0] + p0[1]
  return abs( a*target[0] + b*target[1] + c ) / (a**2 + b**2) ** 0.5
    
def solve(idx):
    global ref
    N = int(sys.stdin.readline())
    if N == 0:
        return False
    points = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
    ref,*points = points

    points.sort(key = cmp_to_key(cmp))

    result = convex_hull([ref] + points)
    length = len(result)
    
    ans = MAX
    for i in range(length) :
        k = (i+1)%length
        tmp = 0.
        for j in range(length) :
            tmp = max(tmp, distance(result[j], result[i], result[k]))
        ans = min(ans, tmp)
    print('Case {:d}: {:0.02f}'.format(idx, math.ceil(ans*100) / 100.0))
    return True

idx = 1
while True:
    if not solve(idx):
        break
    idx+=1

위는 Magentino's 님의 블로그에서 가져온 정답 코드이다.
코드를 보며 어떻게 흘러가는지 확인해 보자.

  1. 정렬
   points.sort(key = cmp_to_key(cmp))

----------------------
def ccw(a,b,c) :
    return (a[0]*b[1] + b[0]*c[1] + c[0]*a[1] ) - (a[1]*b[0] + b[1]*c[0] + c[1]*a[0])

def cmp(a,b) :
    if ccw(ref,a,b) < 0:
        return 1
    else:
        return -1

첫번째, sort 방법이다.
보통 key=lambda 를 많이 쓰지만 정렬 방법도 우리가 설정할 수 있다.
cmp_to_key를 썼는데, CCW를 돌려서 음수가 나오면 우선순위를 높게 준다.

이는 points의 임의의 두점 a,b를 ref를 중점으로 두고 CCW를 했을때,
음수가 나오면 a가 우선, 양수가 나오면 b가 우선이 된다는 것이다.
즉, 점들을 반시계 방향을 기준으로 정렬한다는 것이다.


그렇기에 위를 기준으로 하면,

  • ref = 원점
  • points = [A,B,C]

가 된다는 것이다. 이로써 points로 볼록껍질 연산을 돌려도

중앙의 점이 아닌, 오른쪽 최하단의 점이 우선순위가 높기 때문에
내부의 점을 이은 볼록껍질이 생기지 않는다는 뜻이다.

  1. 볼록껍질 연산

    result = convex_hull([ref] + points)

def convex_hull(points) :
    stk = points[:2]
    for point in points[2:] :
        while len(stk) > 1 and ccw(stk[-2] , stk[-1], point) < 0:
            stk.pop()
        stk.append(point)
    return stk

생각보다는 간단하다.
points에 처음 2점을 잡고(points[0] , points[1])
이를 활용하여 연산을 시작한다.
두 점을 잡는 이유는
아까도 봤다시피 points는 반시계방향으로 정렬되어 있고,
points[0]은 ref이기 때문에 points[0] - poionts[1] 직선은
볼록껍질에 포함된다는 것이 확실해진다.

points[2:]에 대한 연산을 하는데,

이런 모양이 나왔다고 치자.

그렇다면 다음 나올 점(빨간색) 과 마지막에 선택한 점, 그리고 마지막에 이은 직선을 CCW 돌려본다.

성립이 되지 않고, 한번이라도 CCW가 음수가 나온다는건, 볼록껍질에 포함되지 않는다는 것이니 pop한다.

  1. 길이 계산
    여기에 잡기술이 하나 들어간다.
    ans = MAX
    for i in range(length) :
        k = (i+1)%length
        tmp = 0.
        for j in range(length) :
            tmp = max(tmp, distance(result[j], result[i], result[k]))
        ans = min(ans, tmp)

보면서 소름돋았던건데, 그것은 바로

  • k = (i+1)%length

이 부분이다.

밑에서 tmp를 구할때

tmp = max(tmp, distance(result[j], result[i], result[k]))

이 방법을 쓰게 되는데, 잘보면
result[i]와 result[k]가 들어가게 된다.
이는 무슨 뜻이냐면,

(i+1)%length == i+1이지만 i+1 == length이라면 k = 0
이라는 뜻이 되고,

  • 즉 i와 1 차이나지만 한줄로 fault를 피하고 싶다.

라는 뜻을 가지게 된다.

다른 코드를 살펴보자면

    for i in range(length) :
    
	...
    
        for j in range(length) :
            tmp = max(tmp, distance(result[j], result[i], result[k]))

이 되고, 임의의 두 점을 잡은 후 모든 점들과 비교해가면서 나오는 길이의 최대값을 구하겠다는 것이다.
왜 그런지 생각해보자.

우리는 한 도형이 통과할 수 있는 최소한의 길이를 구하고 싶다.

그렇다면

한 직선이 통과할 수 있는 최소한의 거리는
그 직선과 평행한 직선이 접하는 최외곽 점과의 거리
가 될 것이다.

++ 6월 16일 추가

다른 볼록껍질 복습 문제를 풀며 다른 풀이를 적용해보았다.

문제 : https://www.acmicpc.net/problem/9240

cal_1 = []
for i in range(T):
    while len(cal_1) > 1:
        if ccw(cal_1[-2],cal_1[-1],arrow[i]) > 0: 
        ## 부등호 방향은 위/아래가 같으면 상관없음
            break
        cal_1.pop()
    cal_1.append(arrow[i])
    
cal_2 = []
for i in range(T-1,-1,-1):
    while len(cal_2) > 1:
        if ccw(cal_2[-2],cal_2[-1],arrow[i]) > 0:
            break
        cal_2.pop()
    cal_2.append(arrow[i])    
    

cal = cal_1[:-1] + cal_2[:-1]

볼록껍질을 구하는 다른 방법이다.
기존 방법과 차이라고 한다면
기존에는 ccw를 기준으로 정렬을 했지만,
이번에는 그냥 sort()만 해준 후 왼쪽, 오른쪽으로 한번씩 ccw를 돌린다.

이렇게 하는 이유는 다음과 같다.

참고 : https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain

- cal_1은 기준점 하단의 껍질을 구한다.

왜 그런건지 생각해 보아야 한다.

임의의 점들을 생각해보자. 위 점들은 sort() 되었기 때문에
단순 x좌표로 정렬되어 list 안에 번호순대로 정렬되어 있을 것이다.

points = [1,2,3,4,5,6]
## 이렇게 list에 정렬될것임

그렇게, 1->6까지 한번 ccw를 돌렸다고 가정해 보자.

그럼 다음과 같이 선이 연결될 것이다.
여기서 중요한 것은, 

cal_1 = []
for i in range(T):
    while len(cal_1) > 1:
        if ccw(cal_1[-2],cal_1[-1],arrow[i]) > 0:
            break
        cal_1.pop()
    cal_1.append(arrow[i])

위의 식을 한바퀴 돌렸기 때문에 이미 연산이 끝났다는 것이다.
그렇기 때문에 우리는 역순으로 다시 한번 연산을 해야 한다.

역순으로 계산을 하였다.

cal_2 = []
for i in range(T-1,-1,-1):
    while len(cal_2) > 1:
        if ccw(cal_2[-2],cal_2[-1],arrow[i]) > 0:
            break
        cal_2.pop()
    cal_2.append(arrow[i])

곰곰히 생각해본다면, 역순으로 계산하였고, 6번 -> 1번 순으로 연산하였기에
위와 같은 결과가 나온다는것을 알 수 있다.

그렇기에 두가지 계산을 더해주면

다음과 같은 완벽한 볼록껍질을 얻을 수 있다.

복습

왜 처음 코드는 1번만 연산하고, 두번째 코드는 2번 연산해야하는가?

  • 첫번째 코드는 ccw를 기준으로 정렬하였다.

  • 두번째 코드는 단순 X좌표 기준으로 정렬하였다.

  • 첫번째 코드는 1->4->6->5->2 순으로 연산이 될 것이다.

  • 두번째 코드는 1->4->6 , 6->5->2->1 순으로 연산이 될 것이다.

따라서 두 방법 모두 볼록껍질을 온전히 구할 수 있다.















이로서 볼록껍질 코드에 대한 풀이가 끝났다.
다른 사람의 코드를 보고 풀이를 했지만, 한동안은 이걸 풀면서 머리에 넣어야 할거 같다...

profile
김태성
닭이 되고싶은 병아리
이전 포스트

그리디 - HighScore

다음 포스트

회전하는 캘리퍼스

0개의 댓글