[AlgoSpot][Python] 쿼드 트리 뒤집기

📒 문제 설명

🔖 https://algospot.com/judge/problem/read/QUADTREE

📖 문제
대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2^N × 2^N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다.

• 이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b가 됩니다.
• 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w가 됩니다.
• 모든 픽셀이 같은 색이 아니라면, 쿼드 트리는 이 그림을 가로 세로로 각각 2등분해 4개의 조각으로 쪼갠 뒤 각각을 쿼드 트리 압축합니다. 이때 전체 그림의 압축 결과는 x(왼쪽 위 부분의 압축 결과)(오른쪽 위 부분의 압축 결과)(왼쪽 아래 부분의 압축 결과)(오른쪽 아래 부분의 압축 결과)가 됩니다.
  
  쿼드 트리로 압축된 흑백 그림이 주어졌을 때, 이 그림을 상하로 뒤집은 그림 을 쿼드 트리 압축해서 출력하는 프로그램을 작성하세요.

✍ 입력
첫 줄에 테스트 케이스의 개수 C (C≤50)가 주어집니다. 그 후 C 줄에 하나씩 쿼드 트리로 압축한 그림이 주어집니다. 모든 문자열의 길이는 1,000 이하이며, 원본 그림의 크기는 2^20 × 2^20 을 넘지 않습니다.

💻 출력
각 테스트 케이스당 한 줄에 주어진 그림을 상하로 뒤집은 결과를 쿼드 트리 압축해서 출력합니다.

---

✏️ 풀이 과정

📝 1차 시도

• 가장 먼저 생각한 방법은 쿼드 트리의 압축을 해제하고, 픽셀들을 뒤집은 후 그것을 다시 쿼드 트리로 압축하는 것이었다. 압축 해제 및 압축은 사분면을 분할하여 재귀 함수를 호출하는 방식으로 구현할 수 있다.

• decompress 함수의 인자로 original_image의 반복자 it를 사용했다. 함수가 호출될 때마다 it는 original_image의 다음 문자를 가리키게 된다.

• decompress 함수는 쿼드 트리 형식으로 압축된 original_image의 압축을 해제하여 decompressed 배열에 저장한다.

• 위 그림에서 알 수 있듯이 상하로 뒤집은 이미지는 decompressed[::-1]과 같다. 따라서 flipAndCompress 함수에서 decompressed 배열의 가장 아래부터 가장 위까지 차례로 압축하도록 했다.

• MAX_SIZE가 크지 않은 경우에는 이 방법을 사용해도 되겠지만, 이 문제에서 다루는 이미지의 크기는 너무 크기 때문에 적절하지 않다.

✨ 소스 코드

import sys
input = sys.stdin.readline

# 주어진 테스트 케이스의 경우 MAX_SIZE를 16으로 설정해도 정상적으로 출력된다.
# 실제 MAX_SIZE는 1048576이므로 메모리 초과가 발생할 것이다.
MAX_SIZE = 16
decompressed = [['w'] * MAX_SIZE for _ in range(MAX_SIZE)]

def decompress(it, y, x, size):
    head = next(it)
	# 기저 사례: 첫 글자가 'b' 또는 'w'인 경우
    if head == 'b' or head == 'w':
        for dy in range(size):
            for dx in range(size):
                decompressed[y + dy][x + dx] = head

    else:
        half = size // 2
        # 2사분면
        decompress(it, y, x, half)
        # 1사분면
        decompress(it, y, x + half, half)
        # 3사분면
        decompress(it, y + half, x, half)
        # 4사분면
        decompress(it, y + half, x + half, half)

def flipAndCompress(y, x, size):
    result = decompressed[y][x]

    for dy in range(size):
        for dx in range(size):
            if decompressed[y - dy][x + dx] != result:
                half = size // 2
                return (
                    'x' +
                    flipAndCompress(y, x, half) +
                    flipAndCompress(y, x + half, half) +
                    flipAndCompress(y - half, x, half) +
                    flipAndCompress(y - half, x + half, half)
                )
    return result

C = int(input())
for _ in range(C):
    original_image = str(input())
    decompress(iter(original_image), 0, 0, MAX_SIZE)
    print(flipAndCompress(MAX_SIZE - 1, 0, MAX_SIZE))

---

📝 2차 시도

• 각 사분면을 분할하여 재귀 함수를 호출하는 것과 문자열의 반복자를 함수의 인자로 사용하는 방식은 1차 시도와 같지만, 교재에서는 압축을 해제하지 않는 방식을 채택했다.

• 2사분면 → 1사분면 → 3사분면 → 4사분면 순서로 이루어진 이미지를 상하로 뒤집어서 출력하면, 3사분면 → 4사분면 → 2사분면 → 1사분면 순서로 출력된다. 각 사분면에서 다시 나누어지는 사분면의 경우도 같다.

✨ 소스 코드

import sys
input = sys.stdin.readline

def flip(it):
    head = next(it)
    if head == 'b' or head == 'w':
        return head

	# 2사분면
    upper_left = flip(it)
    # 1사분면
    upper_right = flip(it)
    # 3사분면
    lower_left = flip(it)
    # 4사분면
    lower_right = flip(it)

    return 'x' + lower_left + lower_right + upper_left + upper_right

C = int(input())
for _ in range(C):
    original_image = str(input())
    print(flip(iter(original_image)))