[정글 알고리즘] - [상] -백준 10000번 스택_원_영역

 

📋 문제 소개

항목	내용
📌 문제 번호	백준 10000번
🏷️ 난이도	플래 4
📂 분류	스택, 정렬, 좌표 변환
📥 입력	첫 줄 N (1 ≤ N ≤ 100,000), 이후 N개 줄에 원의 중심 x와 반지름 r
📤 출력	원들이 만드는 영역의 수
⏱️ 시간 제한	3초

💬 문제 핵심: x축 위 반원 형태로 놓인 N개의 원이 서로 교차하지 않을 때, 이 원들이 평면을 나누는 영역의 개수를 구하세요.
시작 영역(외부)은 1개이며, 각 원이 등장하면서 새로운 영역을 추가로 만듭니다.

🖼️ 예제 시각화

원의 위치 관계에 따라 영역이 어떻게 나뉘는지 색깔로 확인해 보세요.

예제 1 — N=2, 원 2개가 완전히 분리된 경우 답: 3

📥 Input

2
0 3
7 2

📤 Output

3

영역	색상	설명
① 외부	흰색	두 원 바깥 전체
② A 내부	파랑	원 A 안쪽 (center=0, r=3)
③ B 내부	초록	원 B 안쪽 (center=7, r=2)

영역 합산: 외부(1) + A내부(1) + B내부(1) = 3

예제 2 — N=3, 큰 원 안에 작은 원 2개 답: 4

📥 Input

3
0 5
-2 2
2 2

📤 Output

4

영역	색상	설명
① 외부	흰색	A 바깥 전체
② A 링	파랑	A 내부, B·C 제외한 링
③ B 내부	초록	원 B 안쪽 (center=-2, r=2)
④ C 내부	노랑	원 C 안쪽 (center=2, r=2)

영역 합산: 외부(1) + A링(1) + B내부(1) + C내부(1) = 4

예제 3 — N=4, 2단계 중첩 (A안에 B, B안에 C·D) 답: 5

📥 Input

4
0 6
0 3
-1 1
1 1

📤 Output

5

영역	색상	설명
① 외부	흰색	A 바깥 전체
② A 링	파랑	A 내부, B 제외한 링
③ B 링	초록	B 내부, C·D 제외한 링
④ C 내부	노랑	원 C 안쪽
⑤ D 내부	분홍	원 D 안쪽

영역 합산: 외부(1) + A링(1) + B링(1) + C내부(1) + D내부(1) = 5

💡 핵심 아이디어 도출 과정

#	관찰	설명
1	원의 위치 관계	교차 없으므로 관계는 3가지: 분리 / 포함 / 내접
2	영역 생성 규칙	새 원이 처음 만드는 독립 공간 = +1 영역
3	좌표 변환 💡	원 (x, r) → 구간 (x−r, x+r), 포함 관계를 구간 비교로 판단
4	정렬 기준	왼쪽끝 오름차순 + 동일 왼쪽끝이면 오른쪽끝 내림차순 (큰 원 우선)
5	스택으로 추적	현재 원의 "포함 컨텍스트"를 스택에 유지, 팝 = 해당 원 벗어남

핵심 변환:  원 (x, r)  →  구간 L = x−r,  R = x+r
A가 B를 포함  ⟺  A.L < B.L  &&  B.R < A.R

❌ 단순 쌍 비교가 안 되는 이유: O(N²) 시간 초과 + 중첩 레벨 변화 추적 불가. 스택을 쓰면 O(N) 순회로 해결됩니다.

⚙️ 알고리즘 단계별 설명

단계	동작	의미
1	원 → 구간 변환 (x-r, x+r)	2D→1D 문제 환원
2	정렬 key=(left, -right)	왼쪽 기준 오름차순, 동일이면 큰 원 우선
3	result = 1 초기화	외부 영역 1개 선계산
4	while top.right ≤ left: pop	현재 원을 포함하지 않는 원 제거
5a	스택 비어있음 → result += 1	독립 원 진입 → 새 영역
5b	top.right == right → result+=1 + pop + continue	내접 케이스 → 새 영역, 팝 후 push 생략
5c	그 외 → result += 1	포함 원 안으로 진입 → 새 영역
6	stack.append((left, right))	현재 원을 포함 컨텍스트에 추가

🎬 스텝별 시뮬레이션 — 예제 2

정렬 후: A(-5,5) → B(-4,0) → C(0,4)

원 (L,R)	처리 전 스택	result	처리 후 스택	이유
A(-5,5)	비어있음	result=2	[A]	스택 비어있음 → result+1
B(-4,0)	[A]	result=3	[A,B]	A 내부에 포함 → result+1
C(0,4)	[A,B]	result=4	[A,C]	B(top.right=0) 팝 후 A 내부 → result+1

최종 결과: result = 4 ✓

✅ 최종 풀이 코드 (Python)

boj10000.py — 좌표 변환 + 정렬 + 스택 — O(N log N)

 1import sys
 2input = sys.stdin.readline
 3
 4def solve():
 5    n = int(input())
 6    circles = []
 7    for _ in range(n):
 8        x, r = map(int, input().split())
 9        # 원 (중심, 반지름) → 구간 (왼쪽끝, 오른쪽끝)
10        circles.append((x - r, x + r))
11
12    # 왼쪽끝 오름차순, 같으면 오른쪽끝 내림차순 (큰 원 우선)
13    circles.sort(key=lambda c: (c[0], -c[1]))
14
15    stack = []
16    result = 1  # 외부 영역 1개로 시작
17
18    for left, right in circles:
19        # 현재 원 왼쪽에서 이미 끝난 원 제거
20        while stack and stack[-1][1] <= left:
21            stack.pop()
22
23        if not stack:
24            # 스택 비어있음 = 독립 원 진입 → 새 영역
25            result += 1
26        elif stack[-1][1] == right:
27            # ★ 내접 케이스: 오른쪽 끝이 같음 → 새 영역 후 팝
28            result += 1
29            stack.pop()
30            continue
31        else:
32            # 포함 관계: 스택 top 내부 → 새 영역
33            result += 1
34
35        stack.append((left, right))
36
37    print(result)
38
39solve()

🔎 코드 라인별 설명

라인	코드 요약	설명
1	import sys / input=…	readline으로 입력 속도 최적화
5	n = int(input())	원의 개수 N 입력
10	circles.append((x-r, x+r))	원 (중심,반지름) → 구간 (왼쪽끝,오른쪽끝) 변환
13	circles.sort(key=…)	왼쪽끝 오름차순, 같으면 오른쪽끝 내림차순 (큰 원 우선)
15	stack = [] result = 1	스택 초기화, 외부 영역 1개로 시작
20	while stack and top.right ≤ left	현재 원보다 왼쪽에서 끝난 원 제거
23	if not stack: result+=1	스택 비어있음 = 독립 영역 진입 → +1
26	elif top.right == right	내접 케이스: result+1 후 팝하고 push 생략 (★버그 수정)
31	else: result+=1	포함 원 안으로 진입 → +1
35	stack.append((left, right))	현재 원을 포함 컨텍스트에 추가

⚠️ 내접 케이스 주의 (26~30번 라인):
두 원이 내접할 때 오른쪽 끝점이 동일합니다. 이때 result += 1을 빠뜨리면 영역 1개가 누락됩니다.
또한 내접원은 스택에 push하지 않습니다 (더 이상 안쪽을 가지지 않기 때문).

💡 정렬 기준이 중요한 이유:
같은 왼쪽 끝점일 때 오른쪽 끝점 내림차순 → 큰 원이 항상 먼저 처리되어 포함 관계를 올바르게 스택에 쌓을 수 있습니다.

⏱️ 시간 복잡도 분석

단계	복잡도	이유
구간 변환	O(N)	원 하나당 1번 연산
정렬	O(N log N)	Python Timsort
스택 순회	O(N)	각 원은 push·pop 각 최대 1회
전체	O(N log N)	정렬이 병목

공간 복잡도: O(N) — 스택 최대 N개 저장
N 최대 100,000 → 약 10⁶회 연산, 3초 제한 내 충분

스택 연산이 O(N)인 이유: 각 원은 push 최대 1회, pop 최대 1회 → while 루프 전체 합산 O(N)

🚨 자주 하는 실수 TOP 3

#	실수	올바른 처리
1	내접 케이스에서 result += 1 누락	top.right == right 일 때도 반드시 result += 1
2	정렬 기준을 왼쪽끝만 기준으로 설정	key=(left, -right): 동일 왼쪽일 때 큰 원 우선 처리
3	팝 조건을 < 대신 사용	top.right <= left: 외접(끝점 일치)도 팝 대상

🏁 정리 요약

알고리즘

좌표 변환 + 정렬 + 스택

시간 복잡도

O(N log N)

핵심 발상

원 → 구간 변환으로 포함 관계 단순화

주의 포인트

내접 케이스 result+1 필수

📌 3줄 핵심 요약
1️⃣ 원을 구간으로 변환하고 왼쪽끝 기준으로 정렬 (큰 원 우선)
2️⃣ 스택으로 포함 컨텍스트를 추적하며 영역 카운팅
3️⃣ 내접(오른쪽 끝 동일) 케이스도 반드시 result += 1

🔗 백준 10000번 바로가기