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

문제: BOJ 2630번

풀이

DFS로 덩어리 찾는 문제인줄 알았는데 그냥 분할정복문제였다..
재귀로 정사각형이 아닐때까지 네 사분면으로 나누는 것을 반복하고,
정사각형일때 파란색 색종이인지 하얀색 색종이인지 구별해서 카운트를 올리면 끝이다.

최종코드

import sys
sys.setrecursionlimit(10**9)		#Python에서 재귀를 쓴다면 무조건...
input = sys.stdin.readline

n = int(input())
ar = []
for _ in range(n):
    ar.append(list(map(int, input().split())))
cnt0=0
cnt1=0

def recur(x, y, n):
    global cnt0
    global cnt1
    a = ar[y][x]
    for i in range(y, y + n):		#해당 범위가 전부 같은 색이 아니면 
        for j in range(x, x + n):	#네사분면으로 나눠버리고 다 재귀를 다시 돌린다
            if ar[i][j] != a:
                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 a==0:		#해당 범위가 전부 같은색이면 색에 맞추어 카운트를 올려준다
        cnt0+=1
    else:
        cnt1+=1
recur(0,0,n)
print(cnt0)
print(cnt1)

아니 다 풀어놓고 sys.setrecursionlimit(10^9) 로 해놓고 뭐가 틀렸는지 한참을 찾았다......
파이썬의 제곱연산자는 **라는사실.............