이번 백준 문제는 분할정복으로 푸는 문제이다. 왜냐하면 색깔별 색종이를 구하기 위해선 처음 입력 받은 배열들을 쪼개고 쪼개서 확인하기 때문이다.
1. Divide(분할)
문제를 더 작은 문제들로 해체
보통 절반, 1/4 등 크기를 줄이면서 나누기
2. Conquer(정복)
나눈 작은 문제들을 재귀적으로 해결
작은 문제들이 충분히 작아졌을 땐 직접 해결(보통 기저 조건 도달)
3. Combine(결합)
작은 문제들의 결과값을 바탕으로 원래 문제를 해결
일부 문제는 결합이 필요 없을 수도 있음
아이디어
- 시작점은(0, 0)이고 x,y의 시작점이다.
- 각 x, y 좌표별로 n만큼의 배열들로 이루어진다.
- 분할을 하기위한 시작점으로 각 사각형의 시작점을 좌표로 나타낼 수 있다.
- (x, y) 좌측 상단
- (x, y + n//2) 우측상단
- (x + n//2, y) 좌측 하단
- (x + n//2, y + n//2) 우측 하단
import sys
input = sys.stdin.readline
# 재귀 함수 정의
def recur(x, y, n):
global bule, white
color_paper = paper[x][y] # 기준 색 설정 (첫 칸 기준)
# 현재 영역이 모두 같은 색인지 확인
for i in range(x, x+n):
for j in range(y, y+n):
if color_paper != paper[i][j]:
# 다른 색이 하나라도 있으면 영역을 4개로 분할하여 재귀 호출
recur(x, y, n//2) # 좌측 상단
recur(x + n//2, y, n//2) # 우측 상단
recur(x, y + n//2, n//2) # 좌측 하단
recur(x + n//2, y + n//2, n//2) # 우측 하단
return # 이 호출에서는 더 이상 판단하지 않음
# 색이 모두 동일한 경우, 색에 따라 카운트 증가
if color_paper == 0:
white += 1
else:
bule += 1
# 입력 처리
n = int(input()) # 종이의 한 변의 길이
paper = [list(map(int, input().split())) for _ in range(n)]
bule, white = 0, 0 # 각각 파란색, 흰색 색종이 수
# 전체 영역에 대해 재귀 시작
recur(0, 0, n)
# 결과 출력
print(white, bule, seq='\n')알고리즘
재귀 함수 recur(x, y, n)
(x, y)부터 n x n 크기의 영역에 대해 판단
색이 모두 같으면 해당 색종이 수를 증가
색이 섞여 있다면, 4분할하여 각각 재귀 호출
기저 조건
n == 1인 경우 (더 이상 나눌 수 없는 경우) 자동으로 색이 모두 같다고 판단
영역 분할
4분할 → (좌상단, 우상단, 좌하단, 우하단)
인덱스를 정확히 계산해야 함
시간복잡도
재귀적으로 분할하여 탐색하므로 대략 O(N^2 log N)에 가까움
최대 입력값이 128 x 128이므로 빠르게 동작
아직까지 나에겐 재귀의 요정이 오지않는거 같다ㅠㅠ, 특히 재귀문제에 대해서 오래걸리고 아이디어도 잘 안떠오를 때가 많은데 아직까지 많이 부족해서 많은 경험과 노하우가 쌓여야할거 같다.
