✔ 풀이를 위한 아이디어
- 분할 정복 (Divide and Conquer)
- 재귀 (Recursion)
✔ 코드
import sys
papers = []
count_w = 0
count_b = 0
def check(start_x, start_y, n):
global count_w
global count_b
tmp = papers[start_y][start_x] # 탐색 영역의 첫번째 값을 저장
for j in range(start_y, start_y+n):
for i in range(start_x, start_x+n):
if papers[j][i] != tmp:
check(start_x, start_y, n//2)
check(start_x + n//2, start_y, n//2)
check(start_x, start_y + n//2, n//2)
check(start_x + n//2, start_y + n//2, n//2)
return
if tmp:
count_b += 1
else:
count_w += 1
N = int(input())
for _ in range(N):
papers.append(list(map(int, sys.stdin.readline().split())))
check(0, 0, N)
print(count_w)
print(count_b)- 어려워 보였지만, 생각보다 손쉽게 풀린 문제이다.
- check라는 함수는 탐색하고자 하는 영역 안에 있는 수들이 모두 같은 색인지 아닌지를 판단한다. 만일 모두 같은 색이 아니라면 4개의 영역으로 나누어 재귀적으로 탐색을 진행하고, 모두 같은 색이라면 어떤 색으로 같은지에 따라 count 값을 올려준다.
✔ 관련 개념
- 분할 정복 (Divide and Conquer) 과 재귀 (Recursion)
