[백준][분할 정복] 1992. 쿼드트리 (파이썬/Python)

n = int(input())

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

def quadtree(x, y, n):
    if n == 1:
        return str(m[x][y])
    
    result = []
    for i in range(x, x + n):
        for j in range(y, y + n):
            # 색이 다르면, 다시 분할진행
            if m[i][j] != m[x][y]:
                result.append('(')
                result.extend(quadtree(x, y, n//2))
                result.extend(quadtree(x, y + n//2, n//2))
                result.extend(quadtree(x + n//2, y, n//2))
                result.extend(quadtree(x + n//2, y + n//2, n//2))
                result.append(')')
                return result
            
    return str(m[x][y])
    
print(''.join(quadtree(0, 0, n)))