[백준 python] 10000번 원 영역

[백준 python] 10000번 원 영역

레벨: 플레티넘5

언어: 파이썬

---

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

📑풀이 과정

일단 이 문제는 풀이과정을 다른 사람 블로그를 보고 아이디어를 얻어서 풀이했다.

https://polohee81.tistory.com/51

초기 풀이 아이디어를 보고 싶은 사람은 위의 주소로 접소해서 읽어보길 바란다.

핵심 풀이 아이디어

• x선에 접하는 원의 경계선을 괄호로 생각하고 풀이

위의 원을 괄호로 변환하면

(( )( )) 라고 볼 수 있다.

이 때 안의 원 두개가 사이 공간없이 이어져 있으면 밖의 원의 영역은 2개가 된다.

아래의 사진은 원과의 사이가 벌어져 있어 밖의 원의 영역이 1개이다.

괄호로 변환하면

(( )  ( )  ) 라고 볼 수 있다.

 

1. x축에 접하는 2개의 좌표 리스트에 넣기

입력 받은 원의 중심(x)과 반지름(r)으로 X축에 접하는 2개의 좌표를 구하고

왼쪽 좌표에는 ( , 오른쪽 좌표에는 )

괄호 모양과 함께 리스트에 저장한다.

 

2. 리스트을 정렬한다.

좌표가 오름차순이 되도록 정렬하고 같은 좌표라면 ‘ ) ‘ 괄호가 있는 좌표값을 앞으로 오게한다.

 

3.리스트를 순회하면서 스택에 값을 넣는다.

스택에는 좌표값(position), 괄호모양(bracker), 연결 상태(status) 값을 저장하게 된다.

 

열린괄호 ‘(’ 가 들어올 때

이전에 들어온 좌표값과 비교하여 좌표값이 같으면 원이 접해 있으므로 이전 괄호의 status 값을 1로 바꾼다.

접해있지 않다면 status 값을 0으로 바꾸고 스택에 넣는다.

 

닫힌괄호 ‘)’ 가 들어올 때

스택의 마지막 괄호의 status 값을 확인하고

0이면 하나의 공간으로 +1, 1이면 2개의 공간으로 +2 한다.

그리고 들어있는 스택의 값을 pop()한다.

 

이때 다음 들어오는 괄호의 좌표가 접하였는지 안했는지 확인하여

접하였다면 넘어가고 접하지 않았다면 밖의 원의 괄호 status 값을 0으로 변경한다.

📋풀이 코드

# 원이 들어오는 모양을 괄호로 변환하여 공간 계산
import sys

input = sys.stdin.readline

n = int(input())
circles = []

# 원의 왼쪽은 '(' 모양의 괄호 오른쪽은 ')' 모양의 괄호로 만든다.
for i in range(n):
  x, r = map(int, input().split())
  circles.append((x-r, '('))
  circles.append((x+r, ')'))

# 좌표기준으로 오름 차순으로 정렬하되 좌표가 같으면 ')'모양이 앞에 오게 정렬한다.
circles = sorted(circles, key= lambda x:(x[0], -ord(x[1])))

stack = []
# 스택에는 좌표, 괄호 모양, 상태값이 들어감
answer = 1
for i in range(n*2):
  position, bracket = circles[i]
  if len(stack) == 0:
    stack.append({'pos':position,'bracket':bracket,'status':0})
    continue
  
  # status 0: 기본값 ->
  # status 1: 원 안의 원이 연결 되어 있는 지 확인
  # 괄호가 닫히면 status 값을 확인하고 0 이면 +1 1이면 +2
  if bracket == ')':
    if stack[-1]['status'] == 0:
      answer +=1
    elif stack[-1]['status'] == 1:
      answer +=2
    stack.pop()
    # 원이 이어져 있는지 확인
    if i != n*2-1:
      if circles[i+1][0] != position:
        stack[-1]['status'] = 0
  else:
    if stack[-1]['pos'] == position:
      # 좌표값이 같으면 원이 접해있는 상태
      stack[-1]['status'] = 1
      stack.append({'pos':position,'bracket':bracket,'status':0})
    else:
      # 좌표값이 같지 않으면 원이접하지 않음
      stack.append({'pos':position,'bracket':bracket,'status':0})

print(answer)