BOJ 10000 원 영역

문제 : BOJ 10000 원 영역

주어진 입력으로 표현되는 원으로 만들어지는 영역의 개수를 출력하는 문제이다.
영역은 원 외부를 포함해서 세준다.
예를들어, 원이 1개 있다면 영역의 개수는 2개이다.

접근

문제의 조건에 따라, 모든 원들은 서로 교차하지 않고 접할 수만 있기 때문에
내부에 있는 두개 이상의 원으로 외부의 원이 양분되는 경우 원 하나로 2개의 영역을,
나머지 경우에는 모두 원 하나로 1개의 영역만 만들 수 있다.

따라서, '내부의 원이 외부의 원을 양분하는지' 여부를 판단해서
영역 개수를 +1 또는 +2 해주는 것이 이 문제의 포인트이다.

내부와 외부

'내부의 원이 외부의 원을 양분하는지' 를 판단하기 위해서는
먼저 내부의 원과 외부의 원을 구분할 수 있어야 한다.

원의 중심이 모두 x축 위에 존재한다고 하였으므로,
결국 x축과 원의 양 접접으로 원을 표현 할 수 있다.

예를 들어, 중심 좌표가 3 이고 반지름이 1인 원은
왼쪽 접점이 2, 오른쪽 접점이 4가 된다.

이런 방식으로 원을 표현하게 되면,
각 원의 x축 접점 좌표값의 대소 비교를 통해 원이 안에 있는지, 밖에 있는지 알 수 있다.

외부의 원을 양분하는 내부의 원

이제 내/외부의 원을 구분할 수 있게 되었으니,
내부의 원이 외부의 원을 양분하는지 판단해야 한다.

원들은 교차하지 않는다는 조건에 따라,
외부의 원을 양분하는 내부 원들의 지름 합은 외부 원의 지름과 같다.
다시 말해서,
내부 원들이 외부 원을 양분하나요? 라는 질문은
내부 원들의 지름합이 외부 원의 지름과 같나요? 라는 질문으로 바꿔쓸 수 있다.

구현

먼저 입력된 원을 정렬해주어야 한다.

안쪽에 위치한 원이 외부 원을 양분하는지 확인하기 위해서
바깥쪽 원부터 안쪽 원 순으로 순회하고
같은 깊이에 존재하는 원의 경우에는 생각하기 편하게 왼쪽에서 오른쪽으로 순회하기로 하자.

따라서 가장 왼쪽에 위치한 지름이 가장 긴 원을 먼저 순회할 수 있도록
두 가지 정렬 기준으로 원의 정보가 담긴 배열을 정렬해주었다.

그 다음으로 정렬된 원을 하나씩 꺼내서 비교하는데,
기존에 입력된 원의 정보는 x좌표와 반지름 이므로,
이를 이용해서 해당 원의 왼쪽 접점, 오른쪽 접점을 구해준다.

조건에 따라 영역 개수 늘려주기

'원 위에 원을 쌓아주기 위해' 스택을 이용한다.

각 원을 순회할 때, 현재 탐색중인 원을 포함하는 원이 나타나기 전까지
스택에서 원을 꺼내준다.

이때 마지막에 꺼낸 원은 현재 탐색중인 원과 같은 깊이에 있는 원이다.
이는 외부 원을 현재 탐색중인 원과 함께 '양분할지도 모르는' 원이므로
그 길이를 저장해주어야 한다.

따라서, 스택에 포함되는 원의 정보는 원의 왼쪽, 오른쪽 접점과 함께 원의 지름이 있어야 한다.

이때 원의 지름은 실제 지름이 아닌,
'같은 원에 포함된' '같은 깊이의 원들의 지름의 누적합'을
'현재 원의 지름'과 더한 값이다.

스택에서 조건에 따라 원을 다 꺼낸 뒤,
마지막에 꺼낸 원의 정보에 저장된 길이값과 현재 탐색중인 원의 지름을 합한 값이
탐색중인 원을 포함하는 원의 지름과 같아지면, 그 원은 양분되고, 영역의 수가 하나 더 증가한다.

[ 전체 코드 ]

import sys

n = int(sys.stdin.readline().rstrip())

# 원의 좌표를 정렬
# 정렬 기준
# 1. 원의 왼쪽 시작좌표 오름차순(좌표값이 작은 것 부터)
# 2. 원의 길이 내림차순(길이가 긴 것 부터)
circles = sorted([list(map(int, sys.stdin.readline().split())) for _ in range(n)], key=lambda x: (x[0]-x[1], -x[1]))

def solution():
    stack = []
    count = 1

    for c in circles:
        # 우선 들어온 원에의해 영역수 1 증가함
        count += 1

        # 원의 왼쪽 좌표, 오른쪽 좌표
        l = c[0]-c[1]
        r = c[0]+c[1]
        
        # stack이 비어있는 경우 저장
        if not stack:
            # 순서대로, 원의 왼쪽 좌표, 오른쪽 좌표, 길이(지름)
            stack.append([l, r, r-l])
            
        # stack이 비어있지 않은 경우
        else:
            # 나를 포함하고 있지 않은 원을 모두 제거
            sub_len = 0     # 나를 포함하고 있지 않은 원 중 마지막 원의 길이를 저장할 변수
            while stack and stack[-1][1] <= l:
                sub_len = stack.pop()[2]

            # 나를 포함하고 있지 않던 마지막 원과 내가
            # 나를 포함하는 원을 양분하는지 확인
            if stack and sub_len+r-l == stack[-1][1]-stack[-1][0]:
                # 양분한다면 영역이 2개로 나눠지므로, 영역수를 1 증가
                count += 1
                
            # 현재 원 저장
            # 이때 지름에 sub_len을 더해주는 이유는
            # 이전에 있던 '나를 포함하지 않는 원 중 마지막 원'의 지름을 더한 값으로 
            # '나를 포함하는 원'을 양분하는지 확인하기 위함임
            stack.append([l, r, sub_len+r-l])
    
    return count

sys.stdout.write(f'{solution()}')