[Python] S1_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 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

입력

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

출력

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

조건

시간 제한 2초
메모리 제한 128MB

접근

1. 분할 정복이랑 재귀 함수 사용하면 되겠다.
2. 근데 이제 나눌 때마다 괄호로 묶어주어야하는데, 이걸 어떻게 하지??

코드

import sys
input = sys.stdin.readline

def quadTree(x,y,n):
    global result
    first = video[x][y]  # 초기 숫자
    
    for i in range(x,x+n):
        for j in range(y,y+n):
            # 4등분 해야하는 경우
            if first != video[i][j]:
                result += '('
                quadTree(x, y, n//2)            # 1사분면   
                quadTree(x, y+n//2, n//2)       # 2사분면
                quadTree(x+n//2, y, n//2)       # 3사분면
                quadTree(x+n//2, y+n//2, n//2)  # 4사분면
                result += ')'
                return
    # 동일한 숫자만 나온 경우        
    if first == '0':
        result += '0'
    elif first == '1':
        result += '1'
    
if __name__ == '__main__':
    n = int(input())
    video = [list(input().rstrip()) for _ in range(n)]
    result = ''
    quadTree(0,0,n)
    print(result)

1. 기본적인 틀 자체는 색종이 만들기 문제와 동일하다. (https://velog.io/@hsh111366/Python-S22630%EC%83%89%EC%A2%85%EC%9D%B4-%EB%A7%8C%EB%93%A4%EA%B8%B0)
2. 처음에는 튜플을 사용해야하나.. 고민을 하다가 간단하게 문자열을 추가해주는 방식으로 생각해보았다.
3. 함수를 다시 호출해 4등분을 하는 경우에는 ()안에 넣어주어야 하기 때문에, 1,2,3,4분면을 파악하기 전에 괄호를 열고, 끝나면 닫아준다.

처음에 나온 그림을 예를 들어 설명해보겠다.
초기 상태를 기준으로 1,2,3,4사분면이라고 부르고, 그 하위로는 2-1사분면 ... 2-4사분면 이런 식으로 칭하겠다.

1. 전체의 숫자가 동일하지 않기 때문에, 괄호를 열고 1사분면부터 탐색한다.

2. 1사분면은 모두 0이므로 result에 0을 추가해준다.

   현재 result = (0

3. 다음으로 2사분면을 탐색하던 중 0이 아닌 1을 발견하여 다시 4등분으로 쪼개며 괄호를 열어준다.

   현재 result = (0(

4. 2-1사분면 0, 2-2사분면 0, 2-3사분면 1, 2-4사분면 1로 압축할 수 있기 때문에 result에 0011을 추가해주고 모든 사분면 탐색을 마쳤기에 괄호를 닫아준다.

   현재 result = (0(0010)

이런식으로 끝까지 탐색을 하면 원하는 답을 얻을 수 있다!🙌

느낀 점 & 배운 점

1. 재귀 함수를 잘 쓰면 풀 수 있는 문제들이 많을 듯 하다!
2. 너무 어렵게 생각하지 않는 것도 문제를 풀 때 중요한 것 같다.