백준 1780번 종이의 개수 파이썬 분할 정복 문제 실버 2

쿼드트리와 비슷한데 4개 대신 9개로 나누는 문제

분할정복 기본 유형문제이다. 분할정복을 풀줄 알면 무조건 푸는 문제

---

문제

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

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

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

입력

첫째 줄에 N(1≤N≤3^7, N은 3^k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

---

N = int(input())
maps = []
for i  in range(N):
    a=list(map(int, input().split()))
    maps.append(a)
# N = 9
# maps =[[0, 0, 0, 1, 1, 1, -1, -1, -1],
#  [0, 0, 0, 1, 1, 1, -1, -1, -1],
#  [0, 0, 0, 1, 1, 1, -1, -1, -1],
#  [1, 1, 1, 0, 0, 0, 0, 0, 0],
#  [1, 1, 1, 0, 0, 0, 0, 0, 0],
#  [1, 1, 1, 0, 0, 0, 0, 0, 0],
#  [0, 1, -1, 0, 1, -1, 0, 1, -1],
#  [0, -1, 1, 0, 1, -1, 0, 1, -1],
#  [0, 1, -1, 1, 0, -1, 0, 1, -1]]
cases ={1:0,0:0,-1:0, -99:0}

def divide_conquer(xs,ys,xe,ye):
    global cases
    control= maps[xs][ys] 
    case = control
    for x in range(xs,xe):
        for y in range(ys,ye):
            if maps[x][y] != control:
                case = -99
                break
    if case ==-99:
        Xparam = [xs, (xs*2+xe)//3,(xs+xe*2)//3,xe]
        Yparam = [ys,(ys*2+ye)//3,(ys+ye*2)//3,ye]
        for x in range(len(Xparam)-1):
            for y in range(len(Yparam)-1):
                divide_conquer(Xparam[x],Yparam[y],Xparam[x+1],Yparam[y+1]) 
    else:
      #  print(cases)
        cases[control]+=1
divide_conquer(0,0,N,N)
print(cases[-1])
print(cases[0])
print(cases[1])