Python : 쿼드 트리 (분할정복)

문제

풀이

• 분할정복 + 재귀 문제
• 사각 보드에서 정사각형으로 4등분 했을 때 각 모형에서 모든 값이 0이나 1로 일치할 때 이 배열은 0, 1로 압축할 수 있다.
• 즉 일치하지 않으면 일치하는 정사각형을 찾아서 계속 분할정복을 해주면 된다.

전체 코드

import sys

r = sys.stdin.readline


def cut(x, y, size):
    start = board[x][y]

    for i in range(x, x + size):
        for j in range(y, y + size):
            if start != board[i][j]:
                print('(', end="")
                div = size // 2
                #  vㅁ
                #  ㅁㅁ
                cut(x, y, div)

                #  ㅁv
                #  ㅁㅁ
                cut(x, y + div, div)

                #  ㅁㅁ
                #  vㅁ
                cut(x + div, y, div)

                #  ㅁㅁ
                #  ㅁv
                cut(x + div, y + div, div)
                print(')', end="")
                return
    print(start, end="")


if __name__ == '__main__':
    n = int(r())

    board = list(list(map(int, list(r().strip()))) for _ in range(n))

    cut(0, 0, n)