[1780] 종이의 개수 - Python

/* 문제 */
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.
    1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
    2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.
이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

종이를 4등분하던 앞의 분할정복 문제들과 같은 문제다. 다른 점은 이번에는 종이를 9등분 한다는 것인데 재귀 호출을 9번 작성해야 해서 귀찮긴 했지만 풀이에 어려움은 없었다.

# 정답 코드
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def cut(x, y, n):
    global paper, cnt
    finished = True
    first = paper[x][y]
    for i in range(n):
        if not finished:
            break
        for j in range(n):
            if first != paper[x+i][y+j]:
                finished = False
                break
    
    if finished:
        if first == '-1':
            cnt[0] += 1
        elif first == '0':
            cnt[1] += 1
        else:
            cnt[2] += 1
    else:
        cut(x, y, n//3)
        cut(x, y + n//3, n//3)
        cut(x, y + 2*n//3, n//3)
        cut(x + n//3, y, n//3)
        cut(x + n//3, y + n//3, n//3)
        cut(x + n//3, y + 2*n//3, n//3)
        cut(x + 2*n//3, y, n//3)
        cut(x + 2*n//3, y + n//3, n//3)
        cut(x + 2*n//3, y + 2*n//3, n//3)

n = int(input())
paper = []
cnt =[0, 0, 0]
for _ in range(n):
    paper.append(list(input().strip().split()))
cut(0, 0, n)
for c in cnt:
    print(c)