[백준/Python] BOJ 1780 - 종이의 개수

👀 문제

1780번: 종이의 개수 ✨ 실버 2

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

🔑 키포인트

분할 정복 재귀

✍️ 코드

import sys

n = int(sys.stdin.readline())
paper = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

cnt_minus, cnt_zero, cnt_one = 0, 0, 0

# 중첩 for문 사용 -> 시간은 더 오래 걸리는 듯
def divide(x, y, n):
    global cnt_minus, cnt_zero, cnt_one
    num = paper[x][y]
    for i in range(x, x+n):
        for j in range(y, y+n):
            if num != paper[i][j]:
                # 9개로 분할하기
                for k in range(3):
                    for l in range(3):
                        divide(x + k * n//3, y + l * n//3, n//3)
                return
            
    if num == -1:
        cnt_minus += 1
    elif num == 0:
        cnt_zero += 1
    else:
        cnt_one += 1

divide(0, 0, n)

print(cnt_minus)
print(cnt_zero)
print(cnt_one)