[python] 백준 10000 :: 원 영역 (스택)

[원 영역]

# 문제
x축 위에 원이 N개 있다. 원은 서로 교차하지 않는다. 하지만, 접할 수는 있다.

원으로 만들어지는 영역이 몇 개인지 구하는 프로그램을 작성하시오.

영역은 점의 집합으로 모든 두 점은 원을 교차하지 않는 연속되는 곡선으로 연결될 수 있어야 한다.

# 입력
첫째 줄에 원의 개수 N(1 ≤ N ≤ 300,000)이 주어진다.

다음 N개 줄에는 각 원의 정보 xi와 ri가 정수로 주어진다. xi는 원의 중심 좌표이며, ri는 반지름이다. (-109 ≤ xi ≤ 109, 1 ≤ ri ≤ 109)

입력으로 주어지는 원은 항상 유일하다.

# 출력
첫째 줄에 원으로 인해서 만들어지는 영역의 개수를 출력한다.

0. 풀이 방법

• 주어진 데이터에서 각 원의 왼쪽 점과 오른쪽 점을 구한다.
  왼쪽 점 = 중심 - 반지름, 오른쪽 점 = 중심 + 반지름
• 왼쪽 점부터 오름차순으로 정렬해서 원이 완성되는 시점에 영역의 개수를 증가시킨다.
• 원이 하나 만들어질 때마다 원의 안/밖이 분리되어, 영역이 1 증가한다.
• 원 안에 원들이 꽉 찰 경우에는, 원의 안/밖 말고도 위 아래도 분리되므로 영역이 2 증가한다.

 

1. 각 원의 왼쪽 점과 오른쪽 점을 구한다.

• 주어진 데이터에서 각 원의 왼쪽 점과 오른쪽 점을 구한다.
  왼쪽 점 = 중심 - 반지름, 오른쪽 점 = 중심 + 반지름
• 왼쪽 점인지 오른쪽 점인지의 여부를 L과 R로 구분하고 점의 위치와 함께 저장한다.

for _ in range(n):
    x, r = map(int, sys.stdin.readline().split())
    # '왼쪽 점인지 오른쪽 점인지 여부'와 '점의 위치'를 저장한다.
    circles.append(("L", x - r)) # 왼쪽 점 = 중심 - 반지름
    circles.append(("R", x + r)) # 오른쪽 점 = 중심 + 반지름

 

2. 원의 점들을 정렬한다.

• 정렬의 기준
  1순위) 점의 위치를 오름차순으로 정렬한다.
  2순위) 점의 위치가 같을 경우, 오른쪽 점 R이 왼쪽 점 L보다 앞으로 오도록 정렬한다.
• 원 두 개가 맞닿아 있는 경우에는, 왼쪽 점과 오른쪽 점의 위치가 동일하다.
  이때 왼쪽에 있는 원을 먼저 완성시키고 오른쪽 원을 계산해야 하므로,
  오른쪽 점 R이 먼저 오도록 정렬하는 것이다.

# 오른쪽 점 R이 왼쪽 점 L보다 앞으로 오도록 정렬
circles.sort(key=lambda x: (x[0]),  reverse=True)
# 왼쪽 점부터 오름차순으로 정렬
circles.sort(key=lambda x: x[1])

 

3. 왼쪽 점의 정보를 stack에 담아둔다.

• 왼쪽 점은 원의 시작을 의미한다.
• 이후 반복을 돌면서 오른쪽 점을 만나면 원이 완성된다.
• 이후에 만날 오른쪽 점을 위하여 stack에 담아둔다..

stack = [] # 왼쪽 점과 완성된 원의 정보를 담을 스택
count = 1 # 영역 개수

for circle in circles:
    # 현재 점이 왼쪽 점인 경우들만, stack에 담아둔다.
    if circle[0] == "L":
        stack.append(circle)
        continue

 

4. 왼쪽 점이 아닌 경우, 원을 완성시킨다.

• circles를 돌면서 나오는 circle[0]이 L이 아닌 경우는 (else)
  circle[0]이 R을 의미하며, 이때 가장 최근에 만난 L로 시작한 원이 완성된다.
  (circle에는 L 혹은 R만 넣어놨으니, L이 아니면 R이다,, 당연하쥐...)
• stack에 값이 있다는 것은, 현재 원이 시작되고 나서 아직 원이 닫히지 않았음을 의미한다.
  그러므로 stack의 요소가 있으면 실행하도록 while문 작성!
• 스택에 가장 최근에 쌓인 것을 꺼내서 이전 요소를 의미하는 prev에 담아 둔다.

    # 현재 점이 '오른쪽 점'인 경우에만 아래 코드 수행

    while stack:
        # 스택에 가장 최근에 쌓인 것 꺼냄
        prev = stack.pop()

 

• 가장 최근에 만난 L을 스택에서 꺼낸다면 원이 완성된다.
  (스택에 가장 최근에 쌓인 값이 L이 아닐 수도 있다..! 그건 아래에서 나옴 😄)
• L을 꺼냈다면 원이 완성되었다!
• 원의 너비를 계산한다. (아래에서 필요함)
  너비 = 현재 점(오른쪽 점) - 이전 점(왼쪽 점)

        # L을 꺼낸 경우 == 스택에서 꺼낸 게 왼쪽 점인 경우 -> 원이 만들어짐
        if prev[0] == "L":

            # 너비 = 현재 점(오른쪽 점) - 이전 점(왼쪽 점)
            width = circle[1] - prev[1]

 

• 원이 만들어져서 원의 안/밖으로 영역이 증가했으므로, count를 1 증가한다.
• 원이 만들어지면 stack에 원을 의미하는 C와 위에서 계산한 원의 너비를 추가한다.

            count += 1

            # 원이 만들어졌으므로 stack에 원을 의미하는 C와 너비 추가
            stack.append(("C", width))
			
            # 원이 닫히면 다음으로 넘어간다.
            # 지금 원을 추가했기 때문에 stack에 값이 있어서 break를 안해주면 탈출하지 못한다!!
            break

 

5. stack에서 원을 꺼낸 경우, 너비를 검증한다.

• stack에서 원을 꺼낸 경우, 현재 원 안에 원이 또 존재하는 것을 의미한다.
• 현재 원 안에 있는 원이 여러개인 경우에는, 이 원들이 현재 원을 가득 채우고 있는지 확인해야 한다.
  (이 확인은 아래 6단계에서 할 거임!)
• 현재 원을 가득 채우고 있는지 검증할 때 사용하기 위해 원을 꺼낼 때마다
  total_width에 꺼낸 원의 width를 추가한다.

        # C를 꺼낸 경우 == 스택에서 꺼낸 게 원인 경우 -> 현재 원 안에 존재하는 원을 의미
        elif prev[0] == "C":
            total_width += prev[1]

 

6. 현재 원을 작은 원들이 가득 채우고 있는지 확인한다.

• 현재 원 안에 존재하는 원들의 너비는 total_width에 전부 추가해두었다.
  (stack에서 C를 꺼낼 때마다 추가해놨음)
• 현재 원이 닫힐 때, 현재 원의 너비가 안에 존재하는 원들의 너비 총합과 동일하다면
  작은 원들이 가득 채우고 있는 것이다.
• 현재 원을 가득 채우고 있는 경우에는 원이 위/아래로 분리되므로 count를 2 증가한다.

            # 현재 만들어진 원의 지름이 이전의 원들 지름의 합과 같을 경우
            # 현재 원을 꽉 채우고 있으므로 count를 2 증가
            if total_width == width:
                count += 2

 

• 원이 닫힌 경우와 원들이 현재 원을 가득 채운 경우를 한번에 검증하기 위해 4~6단계의 코드 순서를 변경했다.

        # L을 꺼낸 경우 == 가장 최근에 스택에 쌓인 게 왼쪽 점인 경우 -> 원이 만들어짐
        if prev[0] == "L":

            # 너비 = 현재 점(오른쪽 점) - 이전 점(왼쪽 점)
            width = circle[1] - prev[1]

            # 현재 만들어진 원의 지름이 이전의 원들 지름의 합과 같을 경우
            # 현재 원을 꽉 채우고 있으므로 count를 2 증가
            if total_width == width:
                count += 2
                # 다를 경우, count 1 증가
            else:
                count += 1

            # 원이 만들어졌으므로 stack에 원을 의미하는 C와 너비 추가
            stack.append(("C", width))

            # 원이 닫히면 다음으로 넘어간다.
            # 지금 원을 추가했기 때문에 stack에 값이 있어서 break를 안해주면 탈출하지 못한다!!
            break

        # C를 꺼낸 경우 == 가장 최근에 스택에 쌓인 게 원인 경우 -> 현재 원 안에 존재하는 원을 의미
        elif prev[0] == "C":
            total_width += prev[1]

끝~!

 

전체 코드

import sys
n = int(input())
circles = []
for _ in range(n):
    x, r = map(int, sys.stdin.readline().split())
    # '왼쪽 점인지 오른쪽 점인지 여부'와 '점의 위치'를 저장한다.
    circles.append(("L", x - r)) # 왼쪽 점 = 중심 - 반지름
    circles.append(("R", x + r)) # 오른쪽 점 = 중심 + 반지름

# 오른쪽 점 R이 왼쪽 점 L보다 앞으로 오도록 정렬 (왼쪽 점과 오른쪽 점이 만나는 경우, 닫히는 점인 오른쪽이 먼저 있어야 함)
circles.sort(key=lambda x: (x[0]),  reverse=True)
# 왼쪽 점부터 오름차순으로 정렬
circles.sort(key=lambda x: x[1])

stack = [] # 왼쪽 점과 완성된 원의 정보를 담을 스택
count = 1 # 영역 개수

for circle in circles:
    # 현재 점이 왼쪽 점인 경우들만, stack에 담아둔다.
    if circle[0] == "L":
        stack.append(circle)
        continue

    # 현재 점이 '오른쪽 점'인 경우에만 아래 코드 수행

    # 현재 열린 원 안에 원이 들어있을 경우, 그 원들의 너비를 전부 더해서 담을 변수
    # -> 이게 현재 원의 크기와 같으면 현재 원을 꽉 채우고 있으므로 count를 2 증가시켜줄 예정
    total_width = 0

    while stack:
        # 스택에 가장 최근에 쌓인 것 꺼냄
        prev = stack.pop()

        # L을 꺼낸 경우 == 스택에서 꺼낸 게 왼쪽 점인 경우 -> 원이 만들어짐
        if prev[0] == "L":

            # 너비 = 현재 점(오른쪽 점) - 이전 점(왼쪽 점)
            width = circle[1] - prev[1]

            # 현재 만들어진 원의 지름이 이전의 원들 지름의 합과 같을 경우
            # 현재 원을 꽉 채우고 있으므로 count를 2 증가
            if total_width == width:
                count += 2
                # 다를 경우, count 1 증가
            else:
                count += 1

            # 원이 만들어졌으므로 stack에 원을 의미하는 C와 너비 추가
            stack.append(("C", width))

            # 원이 닫히면 다음으로 넘어간다.
            # 지금 원을 추가했기 때문에 stack에 값이 있어서 break를 안해주면 탈출하지 못한다!!
            break

        # C를 꺼낸 경우 == 스택에서 꺼낸 게 원인 경우 -> 현재 원 안에 존재하는 원을 의미
        elif prev[0] == "C":
            total_width += prev[1]

print(count)