[백준/파이썬] 10000번: 원 영역 핵심 정리

문제 보기 : https://www.acmicpc.net/problem/10000

 

문제 이해하기

이 문제는 바깥 영역을 포함하여 서로 교차하지 않는 원들이 만들어내는 총 영역의 개수를 구해야 합니다. 아래 그림처럼 원들이 바깥 또는 안으로 접해있을 수도 있고, 안에 포함하고 있을 수도 있습니다. 그러면서 각각의 원마다 영역이 하나씩 생기게 됩니다.

이때, 아래 그림처럼 어떤 원(부모 원)의 내부에 있는 자식 원들이 연속적으로 이어져서 부모 원의 지름을 꽉 채우는 경우, 부모 원에 대한 영역이 기존의 한 개가 아닌 두 개가 생기게 됩니다.

이런 식으로 최대 30만 개의 원이 저런 관계들을 가지며 존재하는 상태에서 만들어지는 총 영역의 개수를 구해야 합니다.

 

 

핵심 아이디어

이 문제의 핵심은 부모-자식 원 간의 관계를 트리 구조로 구성하는 것입니다. 새로 추가할 원이 어떤 원의 내부에 위치한다면, 그 원의 자식 노드로 삽입됩니다. 아래 그림은 문제의 예제 테스트 케이스 3번을 기반으로 한 트리 구조 예시입니다. 최상단의 (-1e9, 1e9) 노드는 모든 영역을 감싸는 가상의 바깥 원으로, 바깥 영역을 표현하기 위한 용도입니다.

 

그리고 위의 관계를 만들기 위해서 입력받은 모든 원들을 시작점을 기준으로 오름차순, 시작점이 같다면 끝점을 기준으로 내림차순으로 정렬합니다. 이렇게 정렬하면 자연스럽게 왼쪽에서 시작하는 큰 원부터 안쪽의 작은 원들을 순서대로 처리할 수 있게 되어, 모든 원을 알맞은 위치에 자연스럽게 추가할 수 있습니다.

 

정렬이 끝난 뒤에는, 루트 노드로부터 원 추가 함수를 호출하여 원들을 하나씩 재귀적으로 트리에 삽입합니다. 먼저, 추가할 원의 끝점이 현재 부모 원의 끝점을 벗어나지 않는다면, 이는 해당 원이 부모 원의 자식 원이라는 뜻이므로, 부모 원의 자식 노드로 삽입됩니다.

 

그 다음에는 방금 삽입한 자식 노드에 대해 다시 원 추가 함수를 재귀적으로 호출합니다. 이렇게 하면, 그 다음 원이 자식 원이라면 또 삽입되고, 그 자식에게 다시 함수를 호출하는 일이 계속 반복됩니다.

 

하나의 함수 호출은 다음 두 조건 중 하나를 만족할 때까지 자식 원들을 계속 삽입합니다.

• 더 이상 삽입할 원이 없는 경우
• 추가할 원이 현재 노드의 자식이 아닌 경우

모든 원이 트리에 삽입되었다면, 이제는 각 원이 만드는 영역의 수를 계산할 차례입니다. 이 작업도 마찬가지로 루트 노드부터 재귀적으로 진행됩니다. 함수가 호출되면, 기본적으로 영역을 하나 추가합니다. 그리고 자식 원이 있다면, 각 자식에 대해서도 영역 계산 함수를 재귀적으로 호출합니다.

 

모든 자식 원을 순회한 후에는, 자식 원들의 지름의 합이 현재 원의 지름과 같을 경우, 자식 원들이 부모 원을 꽉 채웠다는 의미이므로 영역을 하나 더 추가로 세어줍니다.

 

루트 노드에서 원 영역 카운트 함수를 호출하는 것에서 시작해 이 과정을 모든 노드에 대해 반복하면, 결과적으로 전체 원들이 만들어내는 영역의 총 개수를 구할 수 있게 됩니다.

 

 

구현하기

먼저, 하나의 원을 표현하기 위해 CircleNode라는 클래스를 정의했습니다. 이 객체는 다음과 같은 정보를 담고 있습니다:

• 시작점 (st)
• 끝점 (en)
• 지름 (dia)
• 자식 원을 저장할 리스트 (children)

이후 등장하는 두 개의 함수는 모두 재귀 함수로 구성되어 있습니다. 각각의 함수는 트리 구조의 핵심 로직을 담당합니다.

• append_circle : 원을 트리에 추가하는 함수
• cal_area : 트리를 순회하며 각 원이 만드는 영역의 개수를 세는 함수

그 다음은 사용자 입력을 처리하는 부분입니다. 모든 원에 대해 중심 좌표 x와 반지름 r을 입력받아, 이를 (x - r, x + r) 형식의 시작점과 끝점으로 변환해 circles 리스트에 저장합니다.

 

이후, 모든 원을 다음 기준에 따라 정렬합니다.

• 시작점 기준 오름차순
• 시작점이 같다면 끝점 기준 내림차순

이렇게 정렬해두면, 큰 원부터 작은 원을 자연스럽게 트리에 삽입할 수 있는 구조가 됩니다.

 

마지막으로, 전체 원을 감싸는 가상의 바깥 원인 루트 노드를 만든 뒤, 해당 루트를 기준으로 append_circle을 호출해 트리를 만들고, 곧이어 cal_area를 호출해 영역 개수를 계산합니다.

 

이 두 함수는 모두 재귀적으로 호출되기 때문에, 모든 원이 트리에 추가되고, 이어서 모든 영역의 개수가 계산됩니다.

 

참고로,

• IDX는 circles 리스트에서 현재 삽입할 원의 인덱스를 추적하기 위한 전역 변수입니다.
• COUNT는 최종적으로 구해질 총 영역 개수를 나타냅니다.

import sys
sys.setrecursionlimit(100000)	# 최대 재귀 깊이를 10만으로 설정
input = sys.stdin.readline
MX = int(1e9)+1

class CircleNode:
    def __init__(self, st, en):
        self.st = st                # 원의 시작점
        self.en = en                # 원의 끝점
        self.dia = en - st          # 원의 지름 
        self.children = []          # 자식 원 목록

def append_circle(node):
    global IDX
    # 더 이상 삽입할 원이 없거나, 다음 원이 현재 노드의 범위를 벗어나는 경우 종료
    while IDX < n and circles[IDX][1] <= node.en:
        child = CircleNode(circles[IDX][0], circles[IDX][1])
        node.children.append(child)
        IDX += 1
        append_circle(child)

def cal_area(node):
    global COUNT
    # 하나의 원에 대해 영역 추가
    COUNT += 1
    # 자식 원들에 대해서 재귀적으로 호출 
    children_diameter_sum = 0
    for child in node.children:
        children_diameter_sum += child.dia
        cal_area(child)
    # 자식 원들이 부모 원을 꽉 채우는 경우 영역 추가
    if children_diameter_sum == node.dia:
        COUNT += 1
       
n = int(input())
circles = []
for _ in range(n):
    x, r = map(int, input().split())
    circles.append((x - r, x + r))
circles.sort(key = lambda x : (x[0], -x[1]))

root = CircleNode(-MX, MX)
IDX, COUNT = 0, 0
append_circle(root)
cal_area(root)

print(COUNT)

 

 

마치면서

평소 많이 접해보지 못했던 기하학적인 알고리즘에 대해 알 수 있는 좋은 시간이었던 것 같습니다. 문제 이해에 도움을 준 든든한 정글 동기 임구철에게 깊은 감사를 전합니다.