[정글 알고리즘] - [하] - 백준 2630번=분할정복(Divide & Conquer) - 색종이 만들기

 

분할정복 + 재귀의 대표 입문 문제입니다.
정사각형 종이를 검사하여 단일 색이면 카운트, 섞여 있으면 4등분하여 재귀 호출하는 구조입니다.
핵심: solve(x, y, size) 함수 하나로 전체 로직을 표현합니다.

📋 문제 정보

항목	내용
문제 번호	백준 2630번
난이도	🟢 실버 II
알고리즘	분할정복, 재귀
입력	첫 줄: N (N = 2^k, 1 ≤ k ≤ 7, 최대 128) 이후 N줄: 각 행의 색 정보 (0=흰색, 1=파란색)
출력	첫 줄: 흰색(0) 색종이 개수 둘째 줄: 파란색(1) 색종이 개수
크기 제한	N ∈ {2, 4, 8, 16, 32, 64, 128} → 항상 2의 거듭제곱

💡 핵심 아이디어: 분할정복 3단계

단계	상황	동작
1️⃣	영역이 전부 0 (흰색)	흰색 종이 카운트 +1, 재귀 종료
2️⃣	영역이 전부 1 (파란색)	파란색 종이 카운트 +1, 재귀 종료
3️⃣	0과 1이 섞여 있음	4등분 → 각 구역에 대해 solve() 재귀 호출

📦 파이썬 2차원 배열 입력 받기

파이썬에는 기본 배열 타입이 없어서 리스트 안에 리스트를 넣어 2차원 구조를 만듭니다.

n = int(input())
paper = []
for _ in range(n):
    paper.append(list(map(int, input().split())))

입력 예시 (N=4)	paper 배열 결과	접근 예시
1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1	[[1,1,0,0],  [1,1,0,0],  [0,0,1,1],  [0,0,1,1]]	paper[2][3] = 1 → 3행 4열 값

⚠️ 흔한 실수:  for i in n: ❌ → n은 정수, 반복 불가 | for i in range(n): ✅
len(input()) ❌ → 문자열 길이 반환 | int(input()) ✅ → 정수값 반환

🏗️ solve(x, y, size) 함수 설계

매개변수	의미
x	검사할 정사각형의 시작 행 (위쪽)
y	검사할 정사각형의 시작 열 (왼쪽)
size	정사각형의 한 변 길이 (size × size 영역 검사)

solve(0, 0, n) 호출 → (0,0)에서 시작하는 n×n 전체 종이 검사

✂️ 4등분 좌표 계산

현재 영역: (x, y)에서 시작, 크기 size
half = size // 2 (항상 정수 나눗셈 사용!)

	y	y+half
x	구역 I solve(x, y, half)	구역 II solve(x, y+half, half)
x+half	구역 III solve(x+half, y, half)	구역 IV solve(x+half, y+half, half)

⚠️ 흔한 실수:
solve(x/2, y/2, size/4) ❌ → 좌표를 절반으로 줄이는 것이 아니라 이동해야 함
size / 2 ❌ → 실수 반환 (인덱스는 정수여야 함) | size // 2 ✅

🌐 global 변수 사용법

파이썬에서 함수 안에서 바깥 변수를 수정하려면 global 선언이 필요합니다.

잘못된 코드	올바른 코드	이유
global w, b # 함수 밖에 위치 w = 0 b = 0 def solve(...): w += 1 # UnboundLocalError!	w = 0 b = 0 def solve(...): global w, b # 함수 안 맨 위 w += 1 # 정상 작동	global은 함수 안에서만 의미 있음 함수 밖 global은 문법 오류 또는 무시됨

파이썬은 함수 안 변수를 기본적으로 지역 변수로 처리합니다.
w += 1을 보면 "지역 변수 w를 만들려는 것?"으로 해석하여 오류 발생 → global w로 해결

✅ 최종 풀이 코드 (주석 포함)

# 분할정복 - 색종이 만들기 (백준 실버2)
# 문제 링크: https://www.acmicpc.net/problem/2630

import sys
input = sys.stdin.readline

n = int(input())
paper = []
for _ in range(n):
    paper.append(list(map(int, input().split())))

# 흰색(0), 파란색(1) 개수 카운터
w = 0
b = 0

def solve(x, y, size):
    global w, b   # 함수 안에서 바깥 변수 수정 선언

    color = paper[x][y]   # 기준색: 이 영역의 (x,y) 칸

    # ① 이 영역이 전부 같은 색인지 검사
    for i in range(x, x + size):
        for j in range(y, y + size):
            if paper[i][j] != color:
                # ② 섞여 있으면 4등분해서 재귀
                half = size // 2
                solve(x,        y,        half)  # 왼쪽 위
                solve(x,        y + half, half)  # 오른쪽 위
                solve(x + half, y,        half)  # 왼쪽 아래
                solve(x + half, y + half, half)  # 오른쪽 아래
                return   # 재귀 후 반드시 종료 (아래 카운트 방지)

    # ③ 여기까지 왔다 = 전부 같은 색 → 카운트
    if color == 0:
        w += 1   # 흰색
    else:
        b += 1   # 파란색

# 전체 종이 검사 시작
solve(0, 0, n)

print(w)
print(b)

⚠️ return 이 왜 필수인가?

return 없는 경우 (버그)	return 있는 경우 (정상)
if paper[i][j] != color: solve(...) # 4번 재귀 solve(...) solve(...) solve(...) # return 없음! # 재귀 후에도 루프가 계속 돌고 # 마지막에 w 또는 b 가 중복 카운트!	if paper[i][j] != color: solve(...) # 4번 재귀 solve(...) solve(...) solve(...) return # 즉시 종료! # 이후 루프 실행 안 함 # 카운트도 안 함 → 정확

핵심: return 아래로 내려왔다 = 전부 같은 색이라는 증거 → 그때만 카운트

🎬 단계별 시뮬레이션 (4×4 예제)

입력:

4
1 1 0 0
1 1 0 0
0 0 1 1
0 0 1 1

종이 배열 (paper):

	j=0	j=1	j=2	j=3
i=0	1	1	0	0
i=1	1	1	0	0
i=2	0	0	1	1
i=3	0	0	1	1

단계	호출	영역	검사 결과	동작
1	solve(0,0,4)	4×4 전체	섞임	half=2, 4등분 재귀 호출
2	solve(0,0,2)	구역I: 왼쪽 위 [1,1][1,1]	전부 1	b += 1 → b=1
3	solve(0,2,2)	구역II: 오른쪽 위 [0,0][0,0]	전부 0	w += 1 → w=1
4	solve(2,0,2)	구역III: 왼쪽 아래 [0,0][0,0]	전부 0	w += 1 → w=2
5	solve(2,2,2)	구역IV: 오른쪽 아래 [1,1][1,1]	전부 1	b += 1 → b=2

✅ 최종 출력: w=2 (흰색 2장), b=2 (파란색 2장)

🌲 재귀 호출 트리 (4×4 예제)

solve(0,0,4)  ← 4×4 전체 [섞임 → 4등분]
├── solve(0,0,2)   ← 구역I  [전부 1 → b+=1]
├── solve(0,2,2)   ← 구역II [전부 0 → w+=1]
├── solve(2,0,2)   ← 구역III[전부 0 → w+=1]
└── solve(2,2,2)   ← 구역IV [전부 1 → b+=1]

결과: w=2, b=2

🔎 핵심 라인 해설

코드	설명
color = paper[x][y]	이 영역의 기준 색 = 맨 첫 칸 (어디든 하나만 잡으면 됨)
range(x, x+size)	전체 n이 아닌 현재 구역만 검사 (range(n)이 아님!)
half = size // 2	정수 나눗셈 필수 (/ 쓰면 2.0이 돼서 인덱스 오류)
4번의 solve() 후 return	재귀 호출 후 즉시 종료 → 아래 카운트 코드 실행 방지
if color == 0: w+=1 else: b+=1	return 없이 여기까지 도달 = 단일색 확정 → 카운트

⏱️ 시간복잡도 분석

케이스	재귀 깊이	각 단계 작업	최악 전체
전부 섞임 (최악)	log₂N	각 셀 최대 1번 방문	O(N²)
단일색	1	N² 검사 후 종료	O(N²)

N=128이면 N²=16,384 → 매우 빠름. 시간 제한 2초 내 충분히 통과.

🚨 자주 하는 실수 TOP 5

#	실수	수정
1	for i in n:	for i in range(n): — n은 정수, range 필요
2	size/2 실수 나눗셈	size//2 — 인덱스는 정수 필수
3	solve(x/2, y/2, size/4) 좌표 오류	solve(x, y+half, half) 등 — 좌표 이동 방식
4	4번 재귀 후 return 없음 → 중복 카운트	재귀 4회 호출 직후 반드시 return
5	global w, b를 함수 밖에 작성	def solve(...): 안 맨 첫 줄에 작성

🏁 핵심 정리

포인트	내용
🔪	분할: 섞인 구역을 half로 4등분 (size//2)
🔁	정복: 단일색이면 카운트, 섞이면 재귀
📍	좌표: (x, y)는 현재 영역 시작점, half씩 이동
↩️	return: 재귀 후 즉시 종료 → 카운트 중복 방지
🌐	global: 함수 안 맨 첫 줄에 선언해야 동작