[BOJ] 2630. 색종이 만들기(python)

📌문제

💪아이디어

1. 정사각형 내 색 체크
   n*n구간 내에 있는 모든 정사각형이 같은 색이어야한다. 가장 첫번째 색을 비교기준으로 색을 비교한다.
   
   • 모두 같으면 비교하는 색의 갯수 증가
     
   • 다르면 구간 나누기
     

1. 색종이 구간 나누기
   정사각형 내 모든 색이 같지 않으면 가로, 세로 n/2으로 나눈다.
   
   • (Ⅰ) 0 <= r < n/2, 0 <= c < n/2
     
   • (Ⅱ) n/2 <= r < n, 0 <= c < n/2
     
   • (Ⅲ) 0 <= r < n/2, n/2 <= c < n
     
   • (Ⅳ) n/2 <= r < n, n/2 <= c < n
     
     

🥂코드

import sys
sys.setrecursionlimit(10**6)
innput = sys.stdin.readline

def chk(paper,x,y,n):
    chk=paper[y][x]
    for i in range(y,y+n):
        for j in range(x,x+n):
            if paper[i][j]!=chk: return False
    answer[chk]+=1
    return True

def divide(paper,x,y,n):
    if not chk(paper,x,y,n):
        divide(paper,x,y,n//2)
        divide(paper,x+n//2,y+n//2,n//2)
        divide(paper,x+n//2,y,n//2)
        divide(paper,x,y+n//2,n//2)
        return    
n = int(input())
paper = []

for _ in range(n):
    paper.append(list(map(int,input().split())))

answer=[0,0] # 하얀색 0 , 파란색 1
divide(paper,0,0,n)
for a in answer: print(a)