[1992] 쿼드트리 - Python

/* 문제 */
흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.
주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 " (0(0011)(0(0111)01)1) "로 표현된다. N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

역시 분할 정복 문제다. 앞서 풀었던 색종이 만들기와 비슷하지만 이번에는 괄호를 적절히 배치해 줘야 한다.

 

예전에 자료구조 수업을 들을 때 괄호의 짝을 맞추기 위해 스택을 사용했던 기억이 있다. 여는 괄호를 추가했다면 닫는 괄호를 스택에 하나 추가해 괄호 안의 내용이 끝나면 pop해서 추가하는 방식이었다. 

이 방법을 문제에 적용해봤다. 분할 정복 문제는 주로 재귀함수로 구현하는데, 재귀함수는 내부적으로 스택처럼 동작한다. 즉 여는 괄호를 추가한 후 재귀적으로 함수를 호출하고 함수 호출이 끝난 후 닫는 괄호를 추가해주면 된다.

# 정답 코드

import sys
input = sys.stdin.readline

def compress(x, y, n):
    global video, res
    first = video[x][y]
    finished = True
    for i in range(n):
        if not finished:
            break
        for j in range(n):
            if video[x+i][y+j] != first:
                finished = False
                break
    if finished:
        res += first
    else:
        res += '('
        compress(x, y, n//2)
        compress(x, y + n//2, n//2)
        compress(x + n//2, y, n//2)
        compress(x + n//2, y + n//2, n//2)
        res += ')'
        
n = int(input())
video = []
for _ in range(n):
    video.append(input().strip())
res = ''

compress(0, 0, n)
print(res)