백준 1780번 "종이의 개수"

문제

백준 1780번 종이의 개수

풀이

쿼드트리를 이용한 분할 정복 문제.

2630번과 비슷한 문제.
4개의 분면으로 나누는 2630번과 달리 9개의 분면으로 나눠야한다.
위 2630번의 풀이처럼 분면마다 재귀를 하면 시간초과가 나길래 수정해 줬다.

Python 코드

import sys
input = sys.stdin.readline

def cut(x,y,n):
    global m_one,zero,one
    check=paper[x][y]
    for i in range(x,x+n):
        for j in range(y,y+n):
            if check!=paper[i][j]:
                #9등분하기
                for a in range(3):
                    for b in range(3):
                        cut(x+n//3*a,y+n//3*b,n//3)
                return
 
    if check==-1:
        m_one+=1
    elif check==0:
        zero+=1
    elif check==1:
        one+=1

n = int(input())
paper = []
one = 0
zero = 0
m_one = 0
for _ in range(n):
  paper.append(list(map(int, input().split())))

cut(0, 0, n)

print(m_one)
print(zero)
print(one)