[BOJ/Python3] 2630번 색종이 만들기

https://www.acmicpc.net/problem/2630

알고리즘 분류
분할정복, 재귀

input = __import__('sys').stdin.readline
N = int(input())

Paper = [list(map(int, input().split())) for _ in range(N)]

W_cnt, B_cnt = 0, 0

def Paper_div(x, y, N):
    global W_cnt, B_cnt
    WB_cnt = 0

    for i in range(x, x + N):
        for j in range(y, y + N):
            if Paper[i][j]:
                WB_cnt += 1

    if not WB_cnt:
        W_cnt += 1
    elif WB_cnt == N**2:
        B_cnt += 1
    else:
        Paper_div(x, y, N//2)
        Paper_div(x+N//2, y, N//2)
        Paper_div(x, y+N//2, N//2)
        Paper_div(x+N//2, y+N//2, N//2)
    return

Paper_div(0, 0, N)
print(W_cnt)
print(B_cnt)

문제풀이
N을 입력받는다.
x번째 줄, y번째 숫자가 0 or 1임을 판단하는 과정을 반복하기 위해 재귀함수를 설계한다.
1. (x, y)를 (0, 0)에서 (N, N)까지 늘려가며 0과 1의 개수를 판단.
2. 모두 0이라면 W 구역 이므로 W_cnt를 1 늘리고 종료
3. 모두 1이라면 B 구역 이므로 B_cnt를 1 늘리고 종료
4. 섞여 있다면 다시 4구역으로 분할하는 과정으로 재귀
1) 시작점 x, y, N//2 칸에 대한 과정
2) 시작점 x+N//2, y, N//2 칸에 대한 과정
3) 시작점 x, y+N//2, N//2 칸에 대한 과정
4) 시작점 x+N//2, y+N//2, N//2 칸에 대한 과정

모든 과정을 수행한 후 W_cnt, B_cnt 출력