백준 1992번: 쿼드트리

백준 1992번: 쿼드트리

아이디어

이미지를 4등분한다. 이미지 사이즈가 1인경우 출력한다. 4등분한 이미지가 각각 0 혹은 1로만 이루어져있으면서 네 이미지 모두 같은 경우 출력한다. 그 외의 경우 여는괄호를 출력하고 함수를 재귀호출하고, 닫는괄호를 출력한다.

코드

N = int(input())
image = [list(map(int, input())) for _ in range(N)]


def cut(num, image):
    size = len(image)
    newImage = []
    if num == 0:  # 왼쪽 위
        for i in range(size//2):
            newImage.append(image[i][:size//2])
    elif num == 1:  # 오른쪽 위
        for i in range(size//2):
            newImage.append(image[i][size//2:])
    elif num == 2:  # 왼쪽 아래
        for i in range(size//2):
            newImage.append(image[i + size//2][:size//2])
    elif num == 3:  # 오른쪽 아래
        for i in range(size//2):
            newImage.append(image[i + size//2][size//2:])
    return newImage


def same(image):
    n = len(image)
    check = image[0][0]
    for i in image:
        for j in range(n):
            if i[j] != check:
                return False
    return True
        

def compress(image):
    if len(image) == 1:
        print(image[0][0], end='')
        return

    lu = cut(0, image)
    ru = cut(1, image)
    ld = cut(2, image)
    rd = cut(3, image)

    if (lu == ru == ld == rd) and same(lu):
        print(lu[0][0], end='')

    else:
        print('(', end='')
        compress(lu)
        compress(ru)
        compress(ld)
        compress(rd)
        print(')', end='')


compress(image)

여담

4등분한 이미지가 서로 같기만 하면 되는 줄 알고 lu == ru == ld == rd로만 조건을 작성했다가 틀렸다.
다 풀고 다른 사람들이 작성한 코드를 봤는데 나처럼 굳이 새로운 배열을 만들 필요가 없었다.
흑흑..