문제 출처 : https://www.acmicpc.net/step/20
문제 파악
정사각형 색종이가 있고, 각 칸은
0→ 하얀색1→ 파란색
으로 색칠되어 있다.
목표는 다음이다.
“더 이상 쪼갤 수 없을 때까지 색종이를 4등분하며 잘랐을 때,
최종적으로 남는 하얀색/파란색 색종이의 개수를 구하라.”
여기서 중요한 조건:
- 현재 보고 있는 정사각형 영역이 모두 같은 색이라면
→ 더 이상 쪼개지 않고 그대로 색종이 1장으로 친다. - 만약 색이 섞여 있다면
→ 정사각형을 4등분해서 각 영역에 대해 다시 같은 과정을 반복한다.
이 구조는 전형적인 분할 정복 패턴이다.
분할 정복 관점에서 구조 잡기
이 문제를 풀 때 핵심은 “어떻게 쪼갤지”가 아니라,
“지금 이 함수가 정확히 뭘 하는 함수인지”를 먼저 정의하는 것이다.
나는 이렇게 정의했다.
divide(x, y, size)
→(x, y)에서 시작하는size × size정사각형 영역을 확인해서
- 전부 같은 색이면: 해당 색(white/blue) 카운트를 1 올리고 종료
- 아니면: 4등분해서 각 작은 정사각형에 대해 다시
divide를 호출
이 정의 하나만 명확히 잡으면,
- 언제 멈출지(Base Case),
- 어디서 4등분할지(Divide),
- 결과를 어떻게 처리할지(Conquer/Combine)
가 자연스럽게 따라온다.
1. Base Case: “단색이면 여기서 끝”
현재 size × size 영역이 전부 0 이거나 전부 1이라면
- 더 이상 쪼개지 않고
white또는blue를 1 증가시키고return으로 함수 종료
여기서 재귀가 멈춘다.
이를 위해 먼저 이 영역이 단색인지 검사하는 코드가 필요하다.
first = matrix[x][y] # 기준 색(첫 칸)
same = True
for i in range(x, x + size):
for j in range(y, y + size):
if matrix[i][j] != first:
same = False
break # 안쪽 j-loop 탈출
if not same:
break # 바깥 i-loop 탈출기준 색 first를 하나 잡고
이 영역의 모든 칸을 훑으면서
하나라도 다른 값이 나오면 → same = False로 표시하고
이중 for문 전체를 즉시 탈출한다.
그 다음:
if same:
if first == 0:
white += 1
else:
blue += 1
return여기서 바로 카운트하고 return → 더 이상 분할 없음.
2. Divide: 4등분해서 재귀 호출
단색이 아니면, 이제 “분할" 을 한다.
정사각형을 4등분하는 패턴은 고정이다.
half = size // 2
# 왼쪽 위
divide(x, y, half)
# 오른쪽 위
divide(x, y + half, half)
# 왼쪽 아래
divide(x + half, y, half)
# 오른쪽 아래
divide(x + half, y + half, half)각 서브 문제도 똑같이
단색인지 검사 → 단색이면 카운트 후 종료
아니면 다시 4등분
을 반복한다.
이 과정이 끝나면, 전역 변수 white, blue에
“최종 색종이 개수”가 모두 누적된다.
여기서는 따로 리턴값을 사용할 필요 없고,
전역 카운터에만 계속 누적하는 구조로 설계했다
해답 및 풀이
import sys
input = sys.stdin.readline
N = int(input())
matrix = []
for _ in range(N):
matrix.append(list(map(int, input().split())))
white = 0
blue = 0
def divide(x, y, size):
"""
(x, y)에서 시작하는 size × size 정사각형 영역을 검사해서
단색이면 white/blue 카운트를 증가시키고,
아니면 4부분으로 분할해 재귀 호출한다.
"""
global white, blue
# 1) 현재 영역의 첫 번째 칸 색을 기준으로 삼는다.
first = matrix[x][y]
# 2) 현재 영역이 전부 같은 색인지 검사한다.
same = True
for i in range(x, x + size):
for j in range(y, y + size):
# 한 칸이라도 다르면 단색 X, 검사 중단
if matrix[i][j] != first:
same = False
break # ① 안쪽 j-loop만 탈출
if not same:
break # ② 바깥 i-loop 탈출
# 3) 만약 단색이라면 → 카운트하고 종료
if same:
if first == 0:
white += 1
else:
blue += 1
return
# 4) 단색이 아니면 여기로 와서 4등분해 분할정복 수행
half = size // 2
# 왼쪽 위
divide(x, y, half)
# 오른쪽 위
divide(x, y + half, half)
# 왼쪽 아래
divide(x + half, y, half)
# 오른쪽 아래
divide(x + half, y + half, half)
# 시작: 전체 영역에서 분할정복 시작
divide(0, 0, N)
print(white)
print(blue)추가로 이 문제의 경우는 2차원 배열이었지만 1차원 배열일 경우의 패턴도 적어둔다.
1차원(구간) 문제 패턴
def divide(l, r):
if l == r:
# 더 이상 쪼갤 수 없는 최소 단위
return ...
mid = (l + r) // 2
left_val = divide(l, mid)
right_val = divide(mid + 1, r)
# 서브 문제 결과를 합치는 부분 (max, min, 합, 등)
return combine(left_val, right_val)3일 후 다시 푼 코드
import sys
input = sys.stdin.readline
N = int(input())
paper = []
for _ in range(N):
paper.append(list(map(int,input().split())))
# 계속 같은 구조로 재귀적으로 검사하는 꼴 , 분할, 정복
# 재귀 없이는 분할정복을 구현하기 어렵지만, 재귀를 쓴다고 다 분할정복은 아니다.
white = 0
blue = 0
# x,y ~ x+size, y+size 영역에 대해 모두 일치하는 지 검사 , 일치하지 않는다면, 분할하며 들어가며 검사
def divide(x,y,size):
global white,blue
base = paper[x][y]
all_same = True
# base와, 영역 모두 색이 일치하지 않는다면 , all_same 을 False로 돌리고 break,break
for i in range(x, x+size):
for j in range(y, y+size):
if base != paper[i][j]:
all_same = False
break
if not all_same:
break
# 모두 일치한다면
if all_same:
# base의 색에 따라 white,blue 증가
if base == 0:
white += 1
else:
blue += 1
return # 지금 이 divide 함수 탈출
# 모두 일치하지 않는다면, 반반씩 쪼개서 divide하며 다시 검사
half = size//2
divide(x,y,half)
divide(x+half,y,half)
divide(x,y+half,half)
divide(x+half,y+half,half)
divide(0,0,N) # (0,0) , size = N 함수 시 작
print(white)
print(blue)