문제 링크는 여기에!

이건 회고에 쓸 만한건 없는데 너무 열심히 풀어서 전체 해설을 쓰기로 했다.
실버한테 플래티넘 문제를 줘서 장장 20시간을 풀게 한 정글..... 너무해...



전체 코드는 주석을 아주 자세하게 달아놓긴 했지만 너무 길어 설명 없이는 읽히지 않을 테니 제일 밑으로 내렸다. 설명부터 보자.

※ 그림이 투명한 배경이라 나이트모드 켜신 분들은 끄고 봐주세요!!!! ※

문제 해석

우선 아이디어의 개요는 이렇다.
모든 원의 중심이 X축 위에 있으므로 우리는 x축만 스캔하면 원의 시작점과 끝점(원이 X축과 만나는 지점)을 모두 확인할 수 있다.
백준에 있는 그림(예제 3)으로 따지면 -20, 2, 12, 20만 확인하면 영역이 몇개인지 알 수 있다는 소리이다.

오른쪽으로 이동하는 점을 l이라고 하면, l이 각 점들을 지나면서 확인할 사항은 다음과 같다.

1. l이 통과하기 시작하는 원(시작점을 지날 때)은 영역을 하나 생성한다.
2. 그런데 그림에서 가장 큰 원([-20,20])처럼 내부의 원들이 꽉 채워서 접하게 되면, 내부가 영역 2, 3으로 나눠져 영역 하나가 추가된다. 이건 외부의 원을 꽉 채웠는지 아닌지를 판단해야 알 수 있기 때문에, 어떤 원인지 저장해 두었다가 원을 완전히 통과했을 때(l이 끝점을 지날 때) 확인할 것이다.
3. N이 1 이상이고 원이 하나 그려지면 배경을 포함해 영역이 두개가 되기 때문에 기본값은 1이다.

아이디어는 간단한데, 2번의 원의 내부에서 꽉 채워서 접했는지를 판단하는게 복잡하다.

---

코드 설명

이제 코드를 같이 보자.

1. circle은 입력받은 원들을 저장할 우선순위 큐이다. 우리는 x-r이 작은 것부터, x-r이 같다면 x+r이 작은 것부터 정렬할 것이다. 그래야 왼쪽에서부터 스캔하면서 점들을 놓치지 않고 작은 것부터 확인할 수 있으니까.
   처음 입력받을 때는 x+r이 앞으로 오게 큐에 넣어서 정렬하고, 뺀 다음에는 x-r이 앞으로 오도록 자리를 바꿔 sorted_circle 배열에 넣어 heapify로 정렬했다.

circle = []
for _ in range(n):
    x, r = list(map(int, stdin.readline().split()))
    heapq.heappush(circle, (x+r, x-r))
    ...

sorted_circle = []
while circle:
    popped = heapq.heappop(circle)
    sorted_circle.append([popped[1], popped[0]])  
heapq.heapify(sorted_circle)

2. stop_point는 l이 확인할 원의 시작점과 끝점을 담은 배열이다. 위의 그림에서는 20, 2, 12, 20만 확인하면 되는데, 1씩 증가하면서 쓸데없는 시간을 낭비할 필요는 없으니까 20, 2, 12, 20을 추가했다. set으로 접하는 부분의 중복을 제거하고 추후에 pop()으로 작은것부터 꺼내기 위해 내림차순 정렬했다.

stop_point = set()    # l이 움직일 지점들, 중복 제거 위해 set
for _ in range(n):
    ...
    stop_point.add(x-r)   
    stop_point.add(x+r)
stop_point = sorted(list(stop_point), reverse=True)

3. passing은 l이 이미 통과중인, 그러니까 시작점을 지난 원의 끝점을 담을 배열이고 answer는 배경 영역때문에 1로 초기화했다. filled는 문제해석 2번에서 이야기 했던 내부가 꽉 채워졌는지 검사해야 할 항목을 넣을 배열이다.
   미리 이야기하자면, 큰 원의 내부가 채워졌는지 검사하기 위해서 내부의 어느 지점까지 채워졌는지와 어디까지 채워져야 할 지를 저장할 것이다.

passing = [] 
answer = 1 
filled = [] 

4. 이제 while문으로 들어가 보자. 여기서부터는 그림이 조금 필요할 것 같다.
   우리는 l을 그림의 시작점에서 오른쪽으로 움직여서 끝점까지 갈 것이기 때문에 내림차순으로 정렬된 stop_point에서 pop으로 가장 작은 값을 꺼내와 l에 할당한다. 그리고 더 이상 꺼내올 것이 없으면 종료한다.
   in_circle은 현재 위치의 l이 만나기 시작하는 원, 그러니까 시작점을 지나는 원을 넣을 배열이다.

while True:
    l = stop_point.pop() 
    in_circle = []    # 이번 l에서 범위 내로 들어오는 원들을 담을 배열

    while ....
    
    if not stop_point:   
        break

5. 두번째 while문을 보자. sorted_circle의 0번째를 꺼내면, sorted_circle은 x-r이 같을 경우 x+r이 작은 것부터 꺼내지기 때문에 파란색 원이 꺼내진다.(=sorted_circle[0]) (지금 도는 while동안 나오는 모든 원은 x-r이 l인 -20이다.) 꺼낸 원의 [0]번째는 원의 시작점이므로, 이것이 l과 같은지 확인하여 현재 l의 위치에서 시작하는 원을 모두 꺼내게 된다.
   그리고 꺼낸 원의 끝점을 passing에 추가한다. 시작점은 이미 지났고, 우리가 궁금한 건 원이 끝났는지이므로 끝점만 넣는다.
   원이 하나 추가될 때 마다 영역이 하나씩 늘어나니까 answer도 하나 추가해준다.
   in_circle은 밑에서 사용할 배열인데, 현재 l의 위치에서 추가되는 모든 원을 모은다. 일단 popped를 추가해두자.

while sorted_circle and sorted_circle[0][0] == l:
        popped = heapq.heappop(sorted_circle)
        in_circle.append(popped)
        heapq.heappush(passing, popped[1])    
        answer += 1   

6. 우리는 아직 시작점이 -20인 원을 하나 더 가지고 있으므로 while문을 한 번 더 돌게 된다. 이번에는 가장 큰 원을 꺼내서 passing에 20을 추가했다.
   

7. while 안에 나오는 if문은 현재 filled 배열이 비어있으니 넘어가자. 더 이상 시작점이 -20인 원이 없으니 첫번째 while문을 빠져나오고 나면 if문과 while문이 하나 더 있다.
   flag를 확인하는 if문 또한 현재와는 상관 없는 블록이다. 윗 줄에서 넘어가자고 했던 while 내부의 if문을 지나야 flag = True가 될 수 있는데, 통과하지 않았으므로 걸리지 않는다.
   5번과 6번에서 passing에 값을 추가했으니 다음 while문을 보자. passing 배열도 작은 값이 맨 앞에 오므로 0번째를 보면 현재 l의 위치에서 아직 통과하지 않은 끝점들 중 가장 작은 값을 보게 된다. 현재는 2인데, l과 같지 않으므로 내부로 들어가지는 않는다.

      if flag_2 and not flag:
        filled[0][0] = saved_mid 

    while passing and passing[0] == l:   
        popped = heapq.heappop(passing)
        if filled and filled[0][0] == popped:    
            heapq.heappop(filled)

8. 사실상 여기가 하이라이트이다.
   5번과 6번에서 새로운 원이 하나 시작될 때 마다 in_circle에 추가해두었는데, 이 길이가 1보다 크다는 것은 이 점에서 시작된 원이 2개 이상이라는 뜻이다. 그리고 한 점에서 시작한 크기가 다른 두 원은 내접할 수 밖에 없다. (외접은 원의 끝점과 시작점이 만난다!)
   우리는 내접하는 원이 있다면 기억해두었다가 내부가 모두 채워지는지 확인해야 하기 때문에 filled 배열에 저장해둔다. in_circle 또한 끝점이 작은 것부터 들어있기 때문에 i != 0으로 가장 작은 원은 넣지 않는다.
   넣는 배열의 [0]번째 값은 나보다 작은 원(in_circle[i-1])이 끝나는 점([1])이다. 이 원은 현재 여기까지 채워져있다는 뜻이다. 편의상 앞으로는 mid라고 부르겠다. [1]번째 값은 현재 원의 끝점으로, 내부가 모두 채워지려면 이 점까지 채워져야 한다. 앞으로는 end라고 불릴 것이다.

if len(in_circle) > 1:  
        for i, c in enumerate(in_circle):
            if i != 0:  
                heapq.heappush(filled, [in_circle[i-1][1],  c[1]])  

9. 다시 while True인 맨 위로 돌아가자. stop_point에서 다음 점을 꺼내 l을 업데이트 했고, in_circle도 빈 배열로 초기화했다.
   여기에서는 플래그 두개와 saved_mid라는 변수가 있다. flag는 밑에서 filled를 new_filled로 교체해야 하는지 판단할 때 쓸 플래그이고, flag_2는 첫 번째 while문을 통과하는지 확인하기 위한 플래그이다. saved_mid는 filled에 저장된 mid값 (=filled[0][0])을 교체하는데 사용할 변수이다.
   현재까지는 무슨 소리인지 알아듣지 못해도 된다. 그저 미리 필요해서 선언해 두었다고 알고 있자.

while True:
    l = stop_point.pop()    
    in_circle = [] 
    flag = False 
    flag_2 = False 
    saved_mid = None

10. 밑의 while문을 들어가서 아까처럼 l의 위치에서 시작하는 원 중 가장 작은 것을 꺼내서 in_circle과 passing에 넣고 answer를 하나 증가시킨다.
    이제는 filled가 빈 배열이 아니므로 if 문을 보면, filled의 [0]번째 값은 내부가 채워졌는지 검사해야 할 원 중 가장 왼쪽의 원을 의미한다. 아까 저장한 mid값이(=filled[0][0]) 현재 새롭게 추가되는 원의 시작점과 같다면(=popped[0]) mid까지 채워진 것을 현재 원이 이어서 채운다는 뜻이다.
    그리고 거기에서 end값과(=filled[0][0]) 현재 원의 끝점까지 같다면(=filled[0][0]), 이어서 채우기 시작해서 끝까지 채웠다는 뜻이 된다. 원을 완벽하게 내접하도록 채웠으므로 영역이 반 나눠져 하나 더 생긴다. answer를 하나 더해준다. 완전히 채워졌으므로 heappop으로 꺼내 검사 대상에서 제외해준다.
    end값과 현재 추가된 원의 끝점이 다르다면, 현재 원이 이어서 채우기는 했으나 끝까지 채운 것은 아니라는 뜻이다.(왼쪽 그림의 경우) 그렇게 되면 추후에 추가되는 원이 마저 채우게 될 수도 있으므로 mid값을 업데이트 해준다.
    여기서 문제인 것은, 우리는 현재 while문을 돌면서 l점에서 시작하는 원을 하나씩 보고 있기 때문에 이 다음 while문에서 더 큰 원이 나와 끝까지 채울 수도 있다.(오른쪽 그림)
    
    그러므로 당장 filled 배열에 업데이트 하지는 않고, saved_mid에 넣어서 가지고 있는다. 만약 뒤에서 나온 원으로 끝까지 채워진다면 flag=True가 되므로 업데이트하지 않으면 된다.
    또한 filled 리스트가 빈 배열인 경우에도 mid를 업데이트 할 수 없으므로 else에 flag=True를 해준다.
    현재 우리는 [2,12]인 원을 보고 있으므로 saved_mid에 12를 넣어준다.

while sorted_circle and sorted_circle[0][0] == l:
        flag_2 = True
        popped = heapq.heappop(sorted_circle)
        in_circle.append(popped) 
        heapq.heappush(passing, popped[1])     
        answer += 1 

        if filled and filled[0][0] == popped[0]:
            if filled[0][0] == popped[1]:
                answer += 1                    
                flag = True 
                heapq.heappop(filled) 
                
            else:
                saved_mid = popped[1]
        else:
            flag = True

11. while문을 한번 더 돌아 [2, 20]인 원을 꺼내자. 자잘한 넣고 빼고 증가하고를 모두 한 뒤, if문을 보면 현재 꺼낸 원의 끝점이 20인데 filled의 end값도 20이므로 이 원이 큰 원을 끝까지 채우게 된다. 영역이 두개로 나뉘어졌으므로 answer 값을 하나 더 올려준다.
    

12. 이제 아까 넘어갔던 flag if문을 볼 수 있다. flag_2=True라는 것은 현재 l의 위치에서 새로 추가된 원이 있다는 뜻인데, flag=False라는 것은 내부가 완전히 채워지지는 않았다는 뜻이므로 저장해두었던 saved_mid로 업데이트 한다. 우리는 완전히 채웠으므로 업데이트하지 않는다.
    l이 끝점을 지나는 원은 완전히 통과한 원이므로 passing 배열에서 지운다. 현재는 [-20,2]의 원을 완전히 지났다. passing 배열은 우선순위 큐이므로 이제 최솟값인 12가 가장 앞으로 온다.
    그런데 방금 제거한 원(=popped)의 끝점이 filled[0]의 mid와 같다면 그 원은 10번의 왼쪽 사진처럼 영영 채워지지 않을 원이므로 검사 목록에서 제거해준다. 우리의 예제에서는 이따 볼 [2,12]의 원이 해당되는 경우이다.

    if flag_2 and not flag:
        filled[0][0] = saved_mid 

    while passing and passing[0] == l: 
        popped = heapq.heappop(passing)
        if filled and filled[0][0] == popped:   
            heapq.heappop(filled)

13. 다시, 현재 l의 위치에서 추가되는 원이 2개이므로 완전히 채워지는지 보기 위해 filled를 업데이트 한다.

if len(in_circle) > 1:  
        for i, c in enumerate(in_circle):
            if i != 0:  
                heapq.heappush(filled, [in_circle[i-1][1],  c[1]])  

14. 처음으로 돌아와 이제 l이 12가 되었다. 여기에서는 새로 추가되는 원이 없으므로 내부의 첫번째 while문은 들어가지 않고 flag의 if문도 지나친다.
    두번째 while문을 보면 현재 끝점을 지나고 있는 원인 [2,12]를 빼낸다. filled의 mid값이 업데이트 되지 않아 이 원의 끝점과 mid 값이 같아지므로 해당 항목은 영원히 영역이 나눠지지 않을 것이다. 따라서 filled에서 빼준다.

    while passing and passing[0] == l:
        popped = heapq.heappop(passing)
        if filled and filled[0][0] == popped:
            heapq.heappop(filled)

15. 드디어 마지막, l = 20이다. 사실상 이미 정답은 나왔고 봐야 할 항목은 모두 끝났다. stop_point가 비어 가장 바깥쪽 while = True문을 나가게 되고 정답을 print한다.
    

---

전체 코드

파이썬 코드이다.

from sys import stdin
import heapq

n = int(stdin.readline())
circle = []
stop_point = set()    # l이 움직일 지점들, 중복 제거 위해 set
for _ in range(n):
    x, r = list(map(int, stdin.readline().split()))
    # x-r이 같을 경우 x+r이 작은 것부터 정렬하기 위해 x+r 정렬 우선
    heapq.heappush(circle, (x+r, x-r))
    stop_point.add(x-r)    # 원이 시작되고 끊기는 모든 지점을 추가
    stop_point.add(x+r)
# pop으로 작은 것부터 꺼낼 수 있도록 내림차순 정렬
stop_point = sorted(list(stop_point), reverse=True)

sorted_circle = []
while circle:
    popped = heapq.heappop(circle)
    sorted_circle.append([popped[1], popped[0]])    # x-r을 기준으로 정렬할 수 있도록 바꿔 넣고
heapq.heapify(sorted_circle)    # heapify로 정렬

passing = []    # l이 이미 통과중인 원의 끝점을 담을 배열
answer = 1    # 배경은 항상 있는 영역이니까 기본 1
filled = []    # 내부가 채워지는지를 검사해야 하는 배열

while True:
    l = stop_point.pop()    # 가장 작은 지점 꺼내서 시작점으로 지정
    in_circle = []    # 이번 l에서 범위 내로 들어오는 원들을 담을 배열
    flag = False    # filled를 new_filled로 교체해야 하는지
    flag_2 = False    # 첫 번째 while문을 통과하는지
    saved_mid = None

    # sorted_circle에 x-r이 작은 것부터, 같으면 x+r이 작은 것 부터 담겨있기 때문에
    while sorted_circle and sorted_circle[0][0] == l:
        flag_2 = True
        popped = heapq.heappop(sorted_circle)
        in_circle.append(popped)     # in_circle에도,
        heapq.heappush(passing, popped[1])     # pierce에도 x-r(x+r)이 작은 것부터 담김
        answer += 1    # 새로운 원이 추가되므로 일단 카운트 하나 올리기

        # 내부가 채워졌는지 알아볼 리스트(filled)에는 끝점이 작은 것 부터, 끝점이 같다면 시작점이 작은 것부터 담김
        # mid까지 채워진 원을 현재 원(popped)이 이어서 채운다면
        if filled and filled[0][0] == popped[0]:
            if filled[0][1] == popped[1]:    # end에서 끝나야 하는 원인데 현재 원의 끝값이 end와 같으면
                answer += 1                      # 끝까지 채워진 원임
                flag = True    # 아래 else문에서의 new_filled를 filled로 복사하지 않아도 됨
                heapq.heappop(filled)    # 검사 대상에서 제외

            else:
                # 현재 원이 이어서 채우기는 했으나 끝까지 채운건 아니라면 일단 mid를 업데이트하지만 filled를 바꿔버리지는 않고 보류
                # 이거 뒤에 추가되는 원에서 끝까지 채울 수도 있음
                saved_mid = popped[1]
        else:
            flag = True    # filled 리스트가 없는 경우에도 mid를 업데이트 하면 안되므로 flag 바꾸기

    # 현재 l의 위치에서 새로 추가된 원은 있으나(flag_2) 내부가 완전히 채워진 원은 없으면(flag)
    if flag_2 and not flag:
        filled[0][0] = saved_mid     # mid를 아까 저장해둔 것으로 업데이트

    while passing and passing[0] == l:    # l이 완전히 통과한 원이면 passing 배열에서 제거
        popped = heapq.heappop(passing)
        if filled and filled[0][0] == popped:    # 방금 제거한 원의 끝점이 filled의 mid와 같다면
            # filled[0]은 영영 채워지지 않을 경우이므로 제거
            heapq.heappop(filled)

    if len(in_circle) > 1:   # 이번에 추가된 원이 두개 이상이면 무조건 하나가 나머지 하나 안에 들어가므로
        for i, c in enumerate(in_circle):
            if i != 0:    # 가장 작은 원을 빼고
                heapq.heappush(filled,    # filled에는 x+r(=end)이 작은 것부터 담김
                               [in_circle[i-1][1],  c[1]])    # 마지막으로 채워진 지점과 끝까지 채워져야 할 지점을 저장
    if not stop_point:    # 끝까지 다 봤으면 break
        break

print(answer)

---

반례

풀면서 입력해봤던 반례들을 모아봤다. 백준 질게에 반례가 하나도 없어서 힘들었기 때문에ㅠ
혹시 풀이를 보고도 이해가 가지 않는다면 아래의 반례 1, 2만 넣어서 디버거로 값을 천천히 살펴보면 무슨 말인지 알 것이다.

input1
10
-1 5
-4 2
-1 1
0 2
3 1
-1 8
15 8
11 4
11 20
27 4
output1
13

input2
10
-1 5
-4 2
-1 1
0 2
3 1
10 5
7 2
10 1
11 2
14 1
output2
13

input3
6
-3 1
-1 1
1 1
3 1
0 4
-2 2
output3
9

input4
6
2 2
7 1
8 2
5 5
3 3
5 1
output4
9

input5
4
1 1
5 1
7 1
4 4
output5
5

input6
4
-2 1
0 1
2 1
0 3
output6
6

input7
3
5 1
7 1
4 4
output7
4

---

생각보다 포스팅이 너무 오래걸렸다. 앞으로는 한 문제를 이렇게 길게 해설하는 일은 없을 것 같다..... 이렇게까지 자세하게 설명했는데 무슨 말인지 모르지는 않겠지!?!!?

중간에 틀렸던 지점들은 다음과 같다.

• passing이나 filled가 정렬된 상태로 들어간다고 생각했는데 아니었다. 생각한 대로 잘 정렬되는지 확인하고 잘 모르겠다면 수동으로 정렬해주는게 안전하다.
• 예외케이스를 잘 생각해야 한다. 난 동기가 말해준 반례 1, 2의 예외케이스를 해결했더니 맞았다. 문제의 예제에 국한해서 생각하지 말고 온갖 기상천외한 예외를 다 생각해보자. 동그라미 외부에 접하지 않고 똑같은 동그라미가 있다거나(반례1), 동그라미 내부에 접하지 않고 똑같은 동그라미가 축소판으로 있다거나(반례2)....