[백준][파이썬] 1992번 쿼드 트리(분할정복2탄)

[핵심]

핵심은 분할정복이였다.

활용 포인트:

-x,y좌표 활용

-()를 어디다가 넣어줄지 생각

 

결국 분할정복1문제와 거의 유사한 패턴이다. 다만, ()로 어디다가( 혹은 )를 넣어줄지

재귀함수 특성을 이용하여 넣어주어야한다.

 

분할정복은 부분적으로 나눠서 검사할때 쓰인다.

num = int(input())
lit= []

for i in range(num):
    t =list(input())
    lit.append(t)
stack = []
def tree(x,y,size,wnt,bnt):
    for i in range(x,x+size):
        for j in range(y,y+size):
            if int(lit[i][j]) == 0:
                wnt += 1
            else:
                bnt +=1
    if wnt == size*size:
        stack.append(0)
        return
    elif bnt == size*size:
        stack.append(1)
        return
    else:
        size = int(size / 2)
        stack.append("(")
        tree(x,y,size,0,0)
        tree(x,y+size,size,0,0)
        tree(x+size,y,size,0,0)
        tree(x+size,y+size,size,0,0)
        stack.append(")")
        return

tree(0,0,num,0,0)
for i in stack:
    print(i,end="")