[Python | 1992] 쿼드트리

https://www.acmicpc.net/problem/1992

---

문제 설명

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

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

 

📌 시간 제한: 2초

---

입력

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

---

출력

영상을 압축한 결과를 출력한다.

---

문제 접근

입력은 0과 1로 구성된 정사각형 형태의 2차원 배열이며, 출력은 이 배열을 압축한 문자열이다. 압축 규칙은 다음과 같다:

• 하나의 영역이 모두 같은 값으로 이루어져 있다면, 해당 값 하나만 출력한다.
• 서로 다른 값이 섞여 있다면, 해당 영역을 4등분하고 각 구역을 다시 같은 방식으로 압축한다.
• 4개의 압축 결과는 괄호로 감싸서 출력한다.

이 규칙을 보면, 어떤 기준에 따라 영역을 나누고 각각의 하위 영역에 동일한 작업을 반복 적용해야 한다. 따라서 이 문제는 전체를 분할해서 같은 로직을 재귀적으로 적용하는 구조, 즉 분할 정복으로 해결할 수 있다.

여기서 중요한 판단은 다음 두 가지다:

1. 현재 영역이 모두 같은 값인지 아닌지를 어떻게 효율적으로 판단할지
2. 같지 않다면, 영역을 정확히 4등분해서 어느 순서로 처리할지

입력 배열의 크기는 항상 2의 거듭제곱 형태이기 때문에, 4등분이 정확히 가능하다. 분할 순서는 문제에 명시된 대로 왼쪽 위 → 오른쪽 위 → 왼쪽 아래 → 오른쪽 아래 순서로 진행해야 한다.

이러한 분석을 바탕으로 문제를 푸는 절차는 다음과 같다:

• 전체 배열을 하나의 영역으로 보고 시작
• 해당 영역이 같은 값으로만 구성되어 있는지 확인
• 같으면 그 값을 출력
• 다르면 네 구역으로 나누어 각 영역에 대해 재귀적으로 압축 수행
• 출력은 괄호로 감싸서 표현

---

구현

n = int(input())
data = [list(input()) for _ in range(n)]

def compress(x, y, size):
    first = data[x][y]  # 현재 영역의 첫 번째 값을 기준으로 비교
    same = True
    for i in range(x, x + size):
        for j in range(y, y + size):
            if data[i][j] != first:
                same = False
                break
        if not same:
            break

    if same:
        print(first, end='')  # 전부 같으면 그 값 출력
    else:
        print('(', end='')  # 섞여있으면 괄호 열고
        half = size // 2
        compress(x, y, half)            # 왼쪽 위
        compress(x, y + half, half)     # 오른쪽 위
        compress(x + half, y, half)     # 왼쪽 아래
        compress(x + half, y + half, half)  # 오른쪽 아래
        print(')', end='')  # 괄호 닫기

compress(0, 0, n)