[백준] 1992 쿼드트리

---

0과 1로 이루어진 이미지 배열을 압축하는 쿼드트리 문제이다.

 

배열의 크기 N이 2의 제곱 수로 주어지는 것을 보았을 때 분할정복 기법으로 쉽게 해결할 수 있다.

 

좌상단, 우상단,  좌하단, 우하단 4가지 배열로 나눌 수 있으며, 각  셀의 값이 모두 동일한 경우에는 해당하는 숫자 하나만 출력하고 그렇지 않을 경우에는 해당하는 셀의 값을 출력해야한다.

 

배열을 나누는 방법으로는 시작 좌표 x, y 와 배열의 크기 n을 통해서 나눌 수 있다.

 

좌상단 = x, y

우상단 = x+n/2, y

좌하단 = x, y+n/2

우하단 = x+n/2, y+n/2

 

from sys import stdin

readline = stdin.readline

def compress_arr():
    arr = input_arr.copy()
    divide(arr, N, 0, 0)

    
def divide(arr, n, row, col):
    # image를 분할하다 한 셀까지 분할하면 그 셀의 값 출력
    if n == 1:
        print(arr[row][col], end="")
        return
    
    flag = True
    for i in range(row, row+n):
        if not flag:
            break
        for j in range(col, col+n):
            if arr[i][j] != arr[row][col]:
                flag = False
                break
    
    # 나눈 한 구역의 값들이 모두 같을 경우 하나만 출력(Compression)
    if flag:
        print(arr[row][col], end="")
    else:
        n = n // 2
        # 4 등분
        print("(", end="")
        divide(arr, n, row, col) # 좌상단
        divide(arr, n, row, col + n) # 우상단
        divide(arr, n, row + n, col) # 좌하단 
        divide(arr, n, row + n, col + n) # 우하단
        print(")", end="")


if __name__ == "__main__":
    N = int(readline())
    input_arr = [list(map(int, list(readline().strip()))) for _ in range(N)]

    compress_arr()