원 영역(백준 10000 -파이썬)

백준에서 처음으로 풀어보는 플레티넘 문제여서 어떻게든 풀어보고 싶었다. 하루종일 걸려서 겨우 풀었다... 이 정도 걸릴 문제는 아닌데 다양한 에러들 수정하느라 너무 오래 걸렸다😢

문제

x축 위에 원이 N개 있다. 원은 서로 교차하지 않는다. 하지만, 접할 수는 있다.
원으로 만들어지는 영역이 몇 개인지 구하는 프로그램을 작성하시오.
영역은 점의 집합으로 모든 두 점은 원을 교차하지 않는 연속되는 곡선으로 연결될 수 있어야 한다.

입력

첫째 줄에 원의 개수 N(1 ≤ N ≤ 300,000)이 주어진다.
다음 N개 줄에는 각 원의 정보 xi와 ri가 정수로 주어진다. xi는 원의 중심 좌표이며, ri는 반지름이다. (-109 ≤ xi ≤ 109, 1 ≤ ri ≤ 109)
입력으로 주어지는 원은 항상 유일하다.

출력

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

예제 입력

2
1 3
5 1

예제 출력

3

문제 풀이

문제 조건을 보면 원은 서로 교차하지 않는다고 말한다.

즉, 어떤 원이 있으면 다른 원은
1. 이 원 안에 있든가
2. 밖에 있든가
3. 아예 곂쳐져 있든가
이세가지 경우밖에 없다.

따라서

if 큰 원 안에 있는 원들의 끝점끼리 이어져 있으면
공간은 두개가 생기고
아니면
공간은 하나가 된다

나는 recursion으로 이 문제를 풀었다.

로직 순서

1. 원의 중심에서 반지름을 빼고 더한 원의 양끝 좌표를 이차원 배열로 만들어 저장한다.
2. 원의 왼쪽 좌표는 내림차순으로 정렬해주고, 왼쪽 좌표가 같다면 오른쪽 좌표를 오름차순으로 정렬해준다.
   이렇게 정렬해주면 왼쪽에서부터 큰 순서대로 저장된다.
3. 각 원들을 돌면서 그 안에 있는 원들의 끝점들이 연결되어 있는지 확인한다.

• 현재 원과 다음 원의 왼쪽 좌표가 같으면 다음 원과 연결된 원을 찾아준다.

4. 끝점들끼리 이어져 있으면 공간 2개를 추가해준다.

코드

import sys
from bisect import  *
sys.setrecursionlimit(10**6)

num = int(input())
circles= []
ans =2
for _ in range(num):
    center , banji=  map(int,sys.stdin.readline().split())
    circles.append([center-banji , center +banji])

circles.sort( key= lambda x:( x[0], -x[1]))

def checking(start_int, end):
    if start_int == num:
        return 0
    elif circles[start_int][1]==end:
        return 1
    elif circles[start_int][1]!=end:
        tmp_int =bisect_left(circles,[circles[start_int][1],]) 
        if circles[tmp_int][0] is not None and circles[tmp_int][0] == circles[start_int][1]:
            return 1* checking(tmp_int,end)
        else:
            return 0
    else:
        return 0

for i in range(num-1):
    if circles[i][0] == circles[i+1][0]:
        if circles[i][1] == circles[i+1][1]:
            ans+=1
        else:
            start_int = bisect_left(circles,[circles[i+1][1],])
            if circles[start_int][0] == circles[i+1][1]:
                if checking(start_int, circles[i][1]) ==1:
                    ans +=2
                else:
                    ans +=1
            else:
                ans+=1
    else:
        ans +=1
print(ans)