[백준/BOJ]#1780: 종이의 개수 [분할정복/재귀/파이썬/python]

https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

분할정복과 재귀를 이용하여 푸는 문제다. 

dfs bfs가 생각났는데 분류가 분할정복으로 되어있고 9개로 종이개수가 정해져있으므로 

for문으로 돌리고 재귀를 해서 체크하면 된다. 

#1780_종이의개수_dividenconquer
n=int(input())

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

res1=0
res0=0
res_1=0

def search(x,y,k):
    global res1, res0, res_1
    checkboard=paper[x][y]
    for i in range(x,x+k):
        for j in range(y,y+k):
            if paper[i][j] != checkboard:
                for a in range(3):
                    for b in range(3):
                        search(x+a*k//3,y+b*k//3,k//3)
                return
            
    if checkboard==-1:
        res_1+=1
    elif checkboard==0:
        res0+=1
    elif checkboard==1:
        res1+=1

search(0,0,n)
print(res_1)
print(res0)
print(res1)