[백준/Python] 10000번 : 원 영역

문제

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

원 n개로 나뉘어지는 영역의 개수를 구하는 문제이다.

모든 원의 중심 좌표는 x축 위에 있고 교차하지 않지만 접할 수 있다.

아래 그림과 같이 원이 접할 경우 총 6개 영역으로 간주됨

풀이

이 문제를 처음 접했을 때 괄호 문제를 떠올렸다.

'('이면 스택에 넣고 ')'이면 스택의 top이 '('인지 확인한 후 pop하면서 cnt+=1해주는 방식

 

원 영역도 똑같이 영역의 개수를 세면 된다.

원의 시작 점, 끝 점을 구한 후 좌표가 작은 순서대로 순회하면서

원의 시작 점이면 스택에 넣고 끝 점이면 스택의 top을 확인 -> top이 시작 점이면 원 하나로 간주하여 시작점을 pop, cnt+=1

 

그러나 이 경우만 고려하면 안 된다.

 

이런 경우는 어떨까..?

 

원 하나가 생길 때마다 카운트를 1씩만 올려주면 안 된다.

그 원 안에 작은 원 여러 개가 존재하는지 확인하고

작은 원들의 지름의 합이 큰 원의 지름과 같다면 두 개의 영역으로 나뉘어지므로 카운트를 2 올려야 한다.

 

예제3

4
7 5
-9 11
11 9
0 20

예를 들어 다음과 같은 경우

먼저 각 원의 시작 점, 끝 점을 구한다.

sides: [[2, 12], [-20, 2], [2, 20], [-20, 20]]

 

정렬 다 했으면 이제 각 좌표의 시작값을 [좌표값, 's'] 끝 값을 [좌표값, 'e']으로 바꿔서 리스트에 저장한다.

그리고 시작 좌표가 가장 작은 것부터, 좌표가 같으면 끝 좌표가 먼저 오도록 정렬한다.

-> 맨 앞에 있고 크기가 작은 원부터 고려하기 위함

-> 그래야 포함 관계의 가장 안쪽에 있는 원부터 영역을 셀 수 있음

sorted: [[-20, 's'], [2, 'e'], [-20, 's'], [20, 'e'], [2, 's'], [12, 'e'], [2, 's'], [20, 'e']]
sorted: [[-20, 's'], [-20, 's'], [2, 'e'], [2, 's'], [2, 's'], [12, 'e'], [20, 'e'], [20, 'e']] # 정렬 후

 

이제 정렬된 좌표를 하나씩 순회하면서 's' 즉 시작점이면 스택에 push, 'e' 즉 끝점이면 스택의 top을 확인한다.

그런데 원 안에 원이 포함되는지 알아야 하므로...........

원이 하나 만들어지면 스택에 만들어진 원을 넣는다.

 

따라서 'e'일 때 스택의 가장 위쪽에 원이 1개, 2개, 3개... 쌓여있고 그 아래에 's'가 존재할 수 있다.

-> while문으로 스택의 top을 계속 꺼내서 원이면 원의 지름을 누적하다가 's'를 만나면 현재 만들어진 원의 지름과 누적된 원의 지름을 비교한다.

-> 두 지름이 같으면 영역이 2개로 나누어졌다는 뜻이므로 cnt+=2

-> 누적된 원의 지름이 더 작으면 영역이 1개이므로 cnt+=1

코드

import sys

n = int(sys.stdin.readline())
circles = []
for _ in range(n):
    circles.append(list(map(int, sys.stdin.readline().split())))

# 각 원의 양쪽 좌표 저장
sides = []
for c in circles:
    sides.append([c[0] - c[1], c[0] + c[1]]) # (중심 좌표 - 반지름, 중심 좌표 + 반지름)

# 시작 좌표 기준으로 정렬, 시작 좌표가 같으면 끝 좌표 기준으로 정렬
sides.sort(key=lambda x: (x[0], x[1]))

# 시작 좌표를 가장 작은 숫자부터, 숫자가 같으면 끝 좌표 먼저 정렬
# 시작 좌표, 끝 좌표를 함께 정렬
sorted = []
for s in sides:
    sorted.append([s[0], 's'])
    sorted.append([s[1], 'e'])

sorted.sort(key=lambda x: (x[0], x[1]))

stk = []
cnt = 0 # 원 영역 개수

for point in sorted:
    total_width = 0 # 안에 원이 여러 개 있을 때 그들의 지름 합
    if point[1]=='s': # 원의 시작 점이면 그냥 넣기
        stk.append(point)
    else: # 원의 끝점이면 영역의 개수를 세어 cnt에 누적
        while stk:
            top = stk.pop()
            if top[1]=='s':
                if total_width==point[0]-top[0]: # 세 원에 의해서 영역이 나뉨
                    cnt+=2
                else: cnt+=1
                stk.append([point[0]-top[0], 'c']) # 원이 하나 만들어짐
                break
            elif top[1]=='c':
                # 너비 누적
                total_width += top[0]

print(cnt+1)