쿼드트리

백준 1992

이 문제도 앞에 색종이 자르기 문제처럼 분할정복 방법으로 똑같이 하면 되는데 출력부분을 좀 신경써야한다.

n = int(input())
img = [list(map(int, input())) for _ in range(n)]

def quad_tree(x,y,n):

    color = img[x][y]
    flag = 0

    for i in range(x, x+n):
        for j in range(y, y+n):
            if color != img[i][j]:
                flag += 1
                break
                
    if flag != 0:
        print("(", end="")
        quad_tree(x, y, n//2)
        quad_tree(x, y+n//2, n//2)
        quad_tree(x+n//2, y, n//2)
        quad_tree(x+n//2, y+n//2, n//2)
        print(")", end="")
    else:
        print(color, end="")
        
quad_tree(0,0,n)

처음 좌표의 값을 color변수에 넣고 for문을 돌면서 해당 좌표 값이 color와 다르면 flag를 증가시키고 탈출한다.
flag가 0이 아니면 color와 달랐다는 뜻이므로 크기를 반씩 줄여서 다시 재귀를 돌린다. 이 때 소괄호도 같이 넣어준다.