소스코드
import sys
import bisect
input = sys.stdin.readline
N = int(input().strip())
circles = []
for _ in range(N):
x,r = map(int, input().strip().split())
circles.append((x-r, x+r)) # 튜플형태로 추가 : (시작점, 끝점)
circles.sort(key=lambda x: (x[0], -x[1])) # 정렬 : 바깥 원이 가장 좌측에 오도록 정렬
count = 0 # 추가로 발생한 영역
# 추가로 발생한 영역에 대해서만 카운트하는 함수
def check_plus_count(outer_circle_idx, inner_circle_idx):
global count
# 안쪽 원의 끝점이 바깥 원의 끝점과 동일한 경우는 추가 영역이 발생했다는 뜻 -> 카운트 + 1
if circles[outer_circle_idx][1] == circles[inner_circle_idx][1]:
count += 1
return
# 안쪽 원의 다음 원 인덱스 확인
next_circle_idx = bisect.bisect_left(circles, (circles[inner_circle_idx][1],))
if next_circle_idx == N:
return
# 안쪽 원의 다음 연결 원이 있다면, 재귀함수 호출
check_plus_count(outer_circle_idx, next_circle_idx)
for i in range(N-1):
if circles[i][0] == circles[i+1][0]:
check_plus_count(i, i+1)
print(N + 1 + count)
Python
복사
풀이
•
우선 바깥 영역과 원의 개수만큼은 무조건 답에 포함됩니다. 다만, 우리가 더 찾아봐야하는 건 “추가로 발생하는 영역입니다”. 무슨 말이냐면, 원 내부의 원들이 모두 접하면서 계속 연결되는 형태라면 바깥 원의 영역은 두 개로 나뉘게 됩니다. 하나의 영역이 더 발생하는 거죠.
•
우선 정렬부터 확인해보겠습니다 :
circles = []
for _ in range(N):
x,r = map(int, input().strip().split())
circles.append((x-r, x+r)) # 튜플형태로 추가 : (시작점, 끝점)
circles.sort(key=lambda x: (x[0], -x[1])) # 정렬 : 바깥 원이 가장 좌측에 오도록 정렬
Python
복사
◦
바깥 원이 가장 좌측에 오도록 튜플의 두 값을 적절히 오름차순/내림차순 정렬했습니다.
▪
시작점을 우선 오름차순 정렬하지만, 시작점이 겹치는 경우에는 끝점의 큰 값이 우선 순위를 갖도록 내림차순하는 겁니다.
•
check_plus_count 함수는 추가 영역에 대해 확인하고 개수를 세는 역할입니다.
◦
함수 바깥 영역의 다음 코드를 보겠습니다 :
for i in range(N-1):
if circles[i][0] == circles[i+1][0]:
check_plus_count(i, i+1)
Python
복사
▪
정렬된 리스트를 순회하면서, i와 i+1의 시작점이 동일하다면, 이는 바깥 원의 내부에 원이 존재한다는 소립니다. 추가 영역의 발생 가능성이 있다는거죠. 그래서 함수를 실행합니다. check_plus_count 는 추가 영역의 개수를 세는 함수니까요.
◦
이제 함수 내부를 설명하겠습니다
▪
우선 안쪽 원의 끝점과 바깥쪽 원의 끝점이 동일하다는건, 안쪽 원들이 계속 이어진 채로 끝점에 도달했다는 의미입니다(마법의 요정이 계속 이어지는 경우에 재귀함수를 실행했다고 믿으세요). 그렇다면 카운트를 증가하고 함수를 종료합니다.
•
내부의 내부까지 확인하는 역할이 아닙니다. 그건 바로 위의 함수 바깥 영역의 코드가 할 일입니다.
▪
아직 원의 끝점에 도달한 게 아니라면 안쪽 원의 다음 원이 있는지 찾습니다. bisect_left 를 이용해서 안쪽 원의 끝점이 시작점이 되는 다음 안쪽 원이 있는지 찾아봅니다.
•
만약 bisect_left 가 반환하는 값이 N이라면, 이는 N-1(리스트 끝 인덱스)까지도 시작점이 해당 값이 되는 경우가 없어서 N번째에 그 값이 들어가야함을 의미합니다. 그럴 경우에는 그냥 함수를 종료합니다(추가 영역 발생 가능성이 없으므로)
•
biscet_left가 반환하는 값이 N이 아니라면, 이는 다음 안쪽 원이 존재한다는 뜻입니다. 재귀를 실행합니다.
•
모든 순회를 마치면 결과를 출력합니다(끝!!)
복기
•
며칠을 코드가 시작할 엄두도 안 나다가 동석 코치님의 트리 구조와 경찬님과 서정님의 스택 기반 코드를 보면서, 갑자기 아침에 “그럼 재귀로 가능할 거 같은데?”라는 생각이 들었습니다.
•
물론 전부 스스로 풀어낸 건 아닙니다. 그렇지만 bisect 모듈이라는 친구를 알게되어서 좋습니다.
•
확실히 우리의 목표는 “추가 영역이 발생하는가?”이다보니, 그 목표에만 초점을 맞춘 코드를 작성하니 훨씬 직관적이라고 느꼈습니다.
•
아마 이진탐색을 사용하다보니 이번 문제에 대해서는 통과를 한 것 같습니다만, 시간복잡도가 그리 좋다고 생각하지는 않습니다
◦
평균 : NlogN 소요시간의 정렬 + N번의 순회에 대해 logN 소요
◦
최악 : NlogN 소요시간의 정렬 + N번의 순회에 대해 NlogN 소요
▪
이진탐색인데 NlogN이 걸리는 이유는, 안쪽 원이 맞닿아 있으면 재귀함수를 실행하는건데, 모두 맞닿아있으면 한 번의 함수 실행이 N번 발생할 수도 있으므로 NlogN이 소요될 수 있습니다.