아니 이걸 어떻게 풀어 (#1708 볼록 껍질)

#1708 볼록 껍질 https://www.acmicpc.net/problem/1708

 

 

진짜 말도안되는 문제이다.

엄청 복잡한 논리적 구조로 접근했는데, 그냥 개념을 알아야 풀 수 있는 문제였다.

 

필요한 개념은 다음 두 가지이다. (기하학 문제이다 보니..)

 

1. Counter Clockwise

세 점 a, b, c가 있을 때, a를 기준으로 b, c가 어느 방향으로 위치하는지를 검사하는 공식이다.

방법은 간단하다. a를 기준으로 두 개의 벡터를 만든다. ab, ac

이 두 벡터를 외적(Cross Products)한다.

 

외적은 특이한 성질이 있는데, 
V X W를 진행했을 때, 결과값이 양수라면 -> V벡터가 W벡터의 오른쪽(시계방향)에 존재한다.

반면, 결과값이 음수라면 V벡터가 W벡터의 왼쪽(반시계방향)에 존재한다.

 

다음 영상을 통해 이 개념을 확립할 수 있다. (한글 자막 지원)

https://www.youtube.com/watch?v=eu6i7WJeinw

 

즉, ab, ac 두 벡터의 외적의 결과값이 음수인 경우,

벡터 ab는 벡터 ac의 왼쪽(반시계방향)에 존재한다.

즉, 점b는 점c의 반시계방향에 존재한다.

 

따라서, 이러한 외적의 성질을 바탕으로 반시계방향으로 존재하는지를 판단할 수 있다.

 

2. Graham Scan (그레이엄 스캔)

이 문제를 풀이하는 실질적인 방법이다.

https://blog.naver.com/bloodsoda/221029163536

[알고리즘(Algorithm)] 컨벡스 헐 알고리즘(Convex Hull) - graham scan

 

다음 블로그에 잘 정리되어 있다.

 

따라서 이 문제는 다음과 같은 순서로 풀이할 수 있다. (그레이엄 스캔 구현)

 

1. 전체 점 중에서 가장 아래 가장 왼쪽에 있는 점을 찾는다. (y, x 순으로 key를 주어 정렬한다)

 

2. 이 점을 제외한 나머지 모든 점들을 Couter ClockWise 공식을 사용해서 정렬한다. (반시계 방향으로 정렬한다.

이 과정이 조금 까다롭다. 나의 경우에는 python을 사용했는데, key에 특정한 함수를 넣어서 원활히 정렬되도록 구현해야만 했다.

이 작업이 끝났을 때, 점의 좌표가 저장된 리스트의 0번 인덱스에는 (1)에서 찾은 가장 아래, 가장 왼쪽에 있는 점이 있어야하고, 1번 인덱스 부터는 반시계방향으로 정렬된 형태여야한다.

 

3. stack에 위에서 정렬한 점들 중 0번과 1번 점을 넣는다.

 

4. 이제 준비는 끝났다. 다음 세 가지 순서를 반복한다.

4-1. 2번 인덱스의 점부터 순차적으로 탐색한다.

4-2-1. 스택 최상단에 있는 두 점을 이은 직선에 대해, 현재 탐색중인 점이 왼쪽(반시계)에 존재한다면 해당 점을 stack에 push 한다.

4-2-2. 만약 그렇지 않다면, stack의 최상단에 있는 값을 버리고, 다시 조건을 확인한다.

 

5. 위 과정이 끝나면, stack에는 convex hull을 구성하는 점들만 남아있게 된다.

 

 

 

 

 

하...  진짜 너무 어려웠다.

잘 고민하고 풀어내길 바란다.

 

 

정답코드

from functools import cmp_to_key

N = int(input().strip())
dots = []
# 1. 입력 받으면서 최대, 최소 좌표를 찾기  : O(n)
for i in range(N):
    x, y = map(int, input().split())
    dots.append([x, y])


def ccw(a, b, c):  # Counter Clockwise 검사.
    # 세 점의 방향을 시계방향인지, 반시계방향인지, 일직선인지 판별하는 수학적 테크닉이다.
    # 벡터의 외적 값을 계산해서 이를 판별할 수 있다.
    # 결과값이 음수인 경우, 반시계방향, 양수인 경우 시계방향, 0인 경우 1직선상에 위치한 점이라는 것이다.
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])


def dist(a, b):  # 점간 거리
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2


# 반시계방향 정렬 함수
def comp(a, b):
    is_clockwise = ccw(pivot, a, b)
    # 1. 두 점 모두 dots[0]과 직선 상에 있으면 가까운 점을 먼저 정렬한다.
    if is_clockwise == 0:
        return dist(pivot, a) < dist(pivot, b)
    # 2. 그게 아니라면,
    else:
        # 음수일 때, 시계방향이기 때문에 음수인 상황을 False로 반환해야 앞쪽으로 배치된다.
        return -1 if is_clockwise > 0 else 1


# Graham Scan의 동작 과정은 다음과 같다.
# 1. 주어진 점들을 반시계방향으로 정렬하고, 정렬된 순서대로 점들을 탐색한다.
# 1-1. Y좌표 기준으로 정렬
dots.sort(key=lambda x: (x[1], x[0]))

pivot = dots.pop(0)
# 1-2. 가장 왼쪽 점을 기준으로 반시계방향 정렬
dots.sort(key=cmp_to_key(comp))
# python sort key에 true, false를 반환하는 함수가 들어간다면, false(0)일 때 앞으로, true(1)일 때 뒤로 간다.
dots.insert(0, pivot)

# 2. stack에 1번 점과 2번 점을 push한다.
stack = [0, 1]
# 3. 3번 ~ N번째 점까지 아래의 과정을 반복할 것이다.
for i in range(2, N):  # i는 현재 탐색하고 있는 점의 index
    # 만약 stack의 최상단에 있는 두 점을 이은 직선 l에 대해, 현재 탐색하는 점이 l의 왼쪽에 존재한다면 stack에 push한다.
    while len(stack) >= 2 and ccw(dots[i], dots[stack[-2]], dots[stack[-1]]) <= 0:
        # 그렇지 않다면 stack을 1번 pop하고 위 조건을 다시 확인한다.
        stack.pop()
    stack.append(i)
# 4. 최종적으로 탐색이 끝나면 stack에는 Convex Hull을 구성하는 점들이 포함되어 있다.

print(len(stack))

# 새로 배운 것.
# Counter Clockwise
# Graham Scan

 

 

아 참, 파이썬에서 cmp함수를 사용해서 정렬하는 방법도 중요하다.

파이썬 sort함수는 기본적으로 정렬의 기준을 삼을 key를 받는다.

따라서, cmp함수를 바로 적용할 수 없다.

functools에서 cmp_to_key를 받아와 적용해야한다.

cmp는 두 입력값을 비교해서 순서를 매겨주는 함수이기 때문에... key와는 다른 적용 방법이 필요하다.