[Python 3] BOJ - 14865 "곡선 자르기"

 # 문제 링크

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

14865번: 곡선 자르기

 

 # 풀이

 개인적으로 이 문제의 핵심은 괄호 문자열이라고 생각한다. 자칫보면 기하학 문제처럼 보일 수 있으나, 문제 구조를 자세히 관찰하면 사실상 스택문제임을 알 수 있다

<그림 1. 4개의 봉우리의 경우>

 위 그림 1에서는 빨간선, 즉 y = 0을 기준으로 상위에 있는 봉우리를 각기 다른 색깔로 칠해놓았다. 현재 봉우리 중 문제에서 어떤 봉우리에도 속하지 않은, 다시 말해 가장 바깥에 있는 봉우리는 파란색 봉우리와 노란색 봉우리임을 알 수 있다. 또한 다른 봉우리를 포함하지 않는 봉우리, 다시 말해 가장 안쪽에 있는 봉우리는 초록색 봉우리 하나뿐이다. 

 그런데, 봉우리의 각 시작점은 무조건 해당 봉우리의 끝점과 대응된다. 그런데, 보란색 봉우리이나 노란색 봉우리처럼 다른 봉우리들을 포함하는 경우에는 반드시 시작점 다음에 끝점이 오지 않는다. 오히려 감싸는 봉우리의 시작점이 그 다음에 오게 된다.

즉, 위의 상황을 괄호 문자열로 생각하게 되면, ()((()))이 됨을 알 수 있고 결국에는 정답은 가장 바깥 괄호쌍과 가장 안쪽 괄호쌍의 갯수를 구하는 것이다.

 그런데 시작점과 끝점을 어떻게 구해야 하는가?

<그림 2. y = 0과의 교점>

 위 그림 2에서 파란색 직선이 시작점과 끝점을 만드는 직선들이다. 파란색 직선들에게는 공통점이 있는데 직선의 y축 기준 값이 양수와 음수 값을 갖는다는 것이다. 그러나, 어떤점이 시작점이고 끝점인지는 아직 알 수 없다. 다만, 이러한 파란색 직선과 빨간색 선이 만나는 점이 모든 시작점과 끝점의 집합임을 알 수 있다.

<그림 3. 시작점과 끝점을 찾는 과정>

 현재 가장 왼쪽 아래에 있는 점을 기준으로 모든 점을 순회한다고 하자. 이 때 그 다음 점이 위 그림 2에서의 파란색 직선, 즉 now의 y값과 next의 y값의 부호가 다르다면 그 선은 반드시 y=0과 교점을 생성하므로 특정 큐에 넣는다.

<그림 4. 시작점과 끝점을 찾는 과정>

 이후의 단계를 나타낸 그림 4이다. 현재 now와 next의 y값의 부호가 같으므로 y=0과의 교점이 없다

<그림 5. 시작점과 끝점을 찾는 과정>

 그림 5에서는 y = 0과의 교점을 다시 찾은 경우를 보여주고 있다. 이 때 큐의 크기가 2가 되고, 그 때 큐의 원소 2개를 특정 리스트에 튜플형태로 저장한다. 이렇게 된다면 시작점과 끝점 쌍을 찾을 수가 있다. 현재 y=0과의 교점이 하나 큐에 있고 입력 순서대로 점들을 순회한다고 가정하자. 그럴 때 다시 y = 0과의 교점이 생겼다는 것은 무조건 양수에서 음수로 내려가거나 반대의 경우이다. 그런데 현재 봉우리에 감싸지는 봉우리를 만들거나 봉우리를 감싸지 않고 새로운 봉우리를 만들려고 할 때 현재의 봉우리를 끝내지 않고서는 만들 수가 없다. 따라서, 마주하는 2개의 교점은 반드시 서로의 시작점과 끝점이 된다

 그런데 시작점은 끝점보다 항상 앞서므로, 둘 중 더 빠른 x값을 갖는 점이 시작점이 되고, 나머지가 끝점이 된다. 가장 바깥 봉우리를 찾는 방법은 간단하다. 모든 시작점과 끝점 쌍을 파악한 후, 일반적인 괄호 문자열 스택문제처럼 구현 후현재 열려있는 시작점이 하나도 없는 순간에 끝난 점이 바깥 봉우리이다.

<그림 6. 바깥쪽 봉우리 도출 과정>

 그림 6에서 이러한 과정이 나타나 있다. 맨 처음 그림 1에서 바깥쪽 봉우리였던 파란 봉우리를 검출하는 과정이다. 현재 오른쪽에 스택에 각 점의 x좌표와 시작 혹은 끝 여부, 인덱스를 넣을 때, 끝인 경우라면 대응되는 시작을 pop해야 한다. 그런데 파란 봉우리, 즉 가장 바깥에 있는 봉우리인 경우는 pop한 후 스택에 아무것도 남아있지 않게 된다. 따라서, 이 때 바깥 봉우리의 갯수를 1 증가시키면 된다.

<그림 7. 안쪽 봉우리 도출 과정>

 위 그림 7은 가장 안쪽 봉우리를 검출하는 과정이다. 매우 간단하다. 현재 끝점의 인덱스와 끝점에 대응되는 시작점의 인덱스가 1차이만 난다면 가장 안쪽 봉우리이다. 실제로 오른쪽 스택의 경우, 그림 1에서 가장 안쪽 봉우리였던 초록 봉우리를 올바르게 검출하는 것을 볼 수 있으며 역시 그림 6에서 가장 바깥쪽 봉우리이자 가장 안쪽 봉우리였던 파란색 봉우리도 이러한 방식으로 검출이 됨을 알 수 있다. 

 

# 코드

import sys, bisect, collections

# 입력부
n = int(sys.stdin.readline())

# zero : y=0인 교점의 x좌표를 저장하는 set
zero = set()
arr = []
for i in range(n):
    a, b = map(int, sys.stdin.readline().split())
    arr.append((a, b))
for i in range(n):
    x1, y1 = arr[i]
    x2, y2 = arr[(i + 1) % n]
    
    # now와 next의 y좌표의 부호가 다른 경우 zero에 추가
    if x1 == x2 and y1 * y2 < 0:
        zero.add(x1)
        
# x좌표 기준 오름차순 정렬
zero = sorted(zero)

# cache : zero에 있는 점들의 x좌표를 key, 인덱스를 value로 갖는 딕셔너리
cache = dict()
for i in range(len(zero)):
    cache[zero[i]] = i

# res : (시작점, 끝점)의 튜플을 저장하는 리스트
res = []

# now : 대응되는 2개의 점을 묶어주는 deque
now = collections.deque()

# check : 현재 인덱스가 방문했는지 점검하는 배열
check = [False] * n
temp = sorted(arr, key=lambda x : (x[0], x[1]))

# 가장 왼쪽 하단에 있는 점의 인덱스를 찾음
val = temp[0]
idx = -1
for i in range(n):
    if arr[i] == val:
        idx = i
        break

# idx가 0이라는 보장이 없으므로 modulo 연산을 통해 원형으로 순회
while not check[(idx + 1) % n]:
    check[idx] = True
    x1, y1 = arr[idx]
    x2, y2 = arr[(idx + 1) % n]
    # y=0의 교점 조건에 만족하면 deque에 삽입
    if x1 == x2 and y1 * y2 < 0:
        now.append(x1)
        # 갯수가 2개라면 대응되는 쌍을 찾았음으로 res에 추가
        if len(now) >= 2:
            first = now.popleft()
            second = now.popleft()
            res.append((min(first, second), max(first, second)))
    idx += 1
    idx %= n

# dots : y=0에서의 교점의 x좌표를 key, (시작/끝을 나타내는 flag, 인덱스)의 튜플을 value로 갖는 딕셔너리
dots = dict().fromkeys(zero)
for i in res:
    idx1 = cache[i[0]]
    idx2 = cache[i[1]]
    dots[i[0]] = (1, idx1)
    dots[i[1]] = (-1, idx2)

# st : 스택 리스트
st = []

# outside : 가장 바깥쪽 봉우리 갯수
outside = 0
# inside : 가장 안쪽 봉우리 갯수
inside = 0

# cnt : 현재 스택안에 남은 좌표의 갯수
cnt = 0
for i in dots:
    # 끝점이라면 스택에서 pop
    if dots[i][0] == -1:
        _, idx = st.pop()
        # 남은 좌표 갯수 1 차감
        cnt -= 1
        # 스택이 빈 경우는 가장 바깥쪽 봉우리이므로 outside 1증가
        if cnt == 0:
            outside += 1
        # 인덱스가 1차이 나는 경우는 가장 안쪽 봉우리이므로 inside 1증가
        if abs(dots[i][1] - idx) == 1:
            inside += 1
            
    # 시작점이면 무조건 스택에 push
    else:
        st.append(dots[i])
        cnt += 1

# 정답 출력
print(outside, inside)