백준 10000번: 원 영역

문제

• https://www.acmicpc.net/problem/10000
• 탐색 대상을 정렬하고 스택을 통해 탐색 과정에서 필요한 정보만 남기기

기록 포인트

• 스택에는 반복의 다음 회차에서 필요한 정보만 남긴다!
  - 더불어, 반복의 다음 회차에서 필요한 정보는 추가해준다!
• 문제를 일반화하여 풀이 가능한 형태로 만들기
  • 원의 포함관계를 확인하려면 왼쪽끝과 오른쪽끝 좌표가 필요하다는 점은 파악
    • 그래서 너비를 기준으로 정렬한 뒤 포함관계에 있는지 확인
    • 본인보다 너비가 작은 원들 중 본인에게 포함되는 원을 찾아 다음 탐색 범위에서 제거
    • 그 결과, 원들 간의 포함 여부를 확인하는 행위가 여러 번 필요해져 시간 초과 발생
  • 하지만 원을 왼쪽끝과 오른쪽끝으로 분리하여 정렬할 수 있다는 점을 생각하지 못했음
    • 원을 두 좌표로 분리하여 좌표를 기준으로 정렬하면 포함관계가 자연스럽게 해결됨
    • 원을 하나의 객체로 유지하지 않아도 필요한 정보는 사라지지 않음

접근 방식

• 문제 내용
  • 수직선 위에 원을 위치시켜 각 원들이 서로 포함관계에 있는지 확인하고,
  • 하나의 원 안에 포함된 여러 개의 원들이 그 원을 가득 채우는지 확인하기
• 필요한 정보로 가공하기
  • 목표
    • 수직선 위에 원의 위치 정보를 표시하기
    • 원들 간의 포함관계 확인하기
  • 서로 포함관계에 있는지 확인하려면, 각 원의 양쪽끝 좌표가 필요함
    • 원의 왼쪽끝: 중점(c) - 반지름(r)
    • 원의 오른쪽끝: 중점(c) + 반지름(r)
  • 원의 위치를 표시하려면, 원의 양쪽끝 좌표를 기준으로 정렬되어야 함
    • 각 원의 왼쪽끝, 오른쪽끝 정보를 각각 (좌표,"L"), (좌표,"R")로 표현
    • 좌표를 기준으로 정렬하여 수직선 위에 원들의 위치를 표시
  • 원 안에 포함된 여러 개의 원들이 그 원을 가득 채우는지 확인해주어야 함
    • 원(C)의 너비 W가 그 원에 포함되는 작은 원(c_1, c_2, ... c_n)들의 너비 w_1, w_2, ... w_n의 합과 일치하면, 그 원은 작은 원들로 가득 찼다고 할 수 있음
      • 이 때, c_n에 포함된 원들의 너비는 중복되므로 고려하지 않음
    • 이를 위해 완성된 원의 정보를 필요한 시점까지 들고 있어야 함
      • L과 R이 만날 때 '완성된 원' 정보로 변환하여 고려할 정보로 추가해주기

• [코드 구성]
  • 1단계: 원을 양끝 좌표값으로 변환하여 정렬하기
    • 좌표 배열 생성
    • 각 원에 대하여
      • 원의 중점(c)과 반지름(r) 정보 확인
      • 왼쪽끝 좌표를 ("L", c-r)로 구성하여 좌표 배열에 추가
      • 오른쪽끝 좌표를 ("R", c+r)로 구성하여 좌표 배열에 추가
    • 좌표와 왼/오 정보를 기준으로 정렬
      • 좌표 기준으로 오름차순으로 정렬
      • 좌표가 동일할 때는 오>왼 순으로 정렬 (문자열 역순 정렬)
  • 2단계: 좌표를 순서대로 탐색하며 영역 개수 세기 (스택에 필요한 정보만 남기기)
    • 스택 생성
    • 영역 개수 1로 설정
    • 각 좌표에 대하여
      • 좌표 속성이 왼쪽끝(L)인 경우
        • (( 새로운 원이 시작되었으므로 고려할 대상에 추가 ))
        • 스택에 추가
      • 좌표 속성이 오른쪽끝(R)인 경우
        • (( 하나의 원이 종료되었으므로 스택에 담긴 정보를 바탕으로 생성되는 영역의 개수를 확인 ))
        • 스택의 가장 뒤에 있는 정보(prev)부터 차례대로 탐색하기
          • prev를 스택에서 pop
          • prev의 속성이 하위 원(C)인 경우
            • 하위 원의 너비 누적
          • prev의 속성이 왼쪽끝(L)인 경우
            • (( 새로운 원이 생성되었음 ))
            • 하위 원 너비의 누적된 합이 새로운 원 너비와 동일한 경우
              • 하위 원으로 가득 찼다고 판단하여 영역 개수 2 증가
            • 하위 원 너비의 누적된 합이 새로운 원 너비보다 작은 경우
              • 가득 차지 않았으므로 영역 개수 1 증가
            • 새로운 원을 ("C", 너비값)으로 구성하여 스택에 추가
              • (( 새로운 원은 다음에 완성될 원에 포함될 수 있기 때문에, 새로운 원의 너비값은 반복의 다음 회차에서 고려 대상임 ))
            • 스택 탐색 종료

제출 답안

최종 답안

• array of tuple을 정렬할 때 팁
  • 좌표인 숫자(p[1])는 오름차순, L/R 문자(p[0])는 내림차순
  • 이를 위해 숫자 p[1] 앞에 마이너스를 붙여 역순으로 처리한 뒤,
  • 다시 reverse 파라미터를 True로 설정해 다시 전체를 역순 처리
  • (문자인 p[0] 앞에 마이너스를 붙이면 TypeError 발생함)
  • 참고 링크

import sys
N = int(sys.stdin.readline())

points = []
for _ in range(N):
    c, r = list(map(int, sys.stdin.readline().split()))
    points.append(("L", c-r))
    points.append(("R", c+r))

# 좌표 기준 정렬    
points.sort(key=lambda p: (-p[1], p[0]), reverse=True)

# 차례대로 돌며 확인
stack = []
area = 1
for curr in points:
    # 왼쪽끝인 경우
    if curr[0] == "L":
        stack.append(curr)
        continue
    # 오른쪽끝인 경우
    cum_width = 0
    while stack:
        prev = stack.pop()
        # 본인 내부에 원이 있었으면, 해당 원의 너비를 누적
        if prev[0] == "C":
            cum_width += prev[1]        
        # R이 나올 때마다 L를 pop해주므로 처음 만난 L이 본인과 동일한 원에서 나온 값
        elif prev[0] == "L":
            # 원의 너비 계산
            width = curr[1] - prev[1]
            # 내부에 있는 원들의 너비 합산이 본인의 너비와 일치하는지 확인
            if width == cum_width:
                area += 2
            else:
                area += 1
            # 다른 원에 포함될 수 있으므로 추가
            stack.append(("C", width)) 
            break
    
print(area)