[Silver I] 쿼드트리 - 1992

문제 링크

성능 요약

메모리: 31256 KB, 시간: 56 ms

분류

분할 정복, 재귀

문제 설명

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(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의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력

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

---

풀이

아이디어

이때까지 풀이한 문제랑 비슷하나, 출력 형식을 조금 고민해야 했던 문제.
어떻게 나눌것인가가 중요한데, $n/2$로 분할하여, set을 이용해 집합에 같은 원소가 몇개인지 확인 후 그 크기가 1이거나 s가 1인 경우 값을 return, 그 이외의 경우 재귀를 이용하여 범위의 1사분면 부터 4사분면까지 탐색하는 방식을 사용하였다.

재귀 코드 자체는 너무나 똑같지만, 괄호를 열고 닫고 하는 부분에서 재귀의 동작 과정을 생각해야 하는 문제였다.

코드

N = int(input())
graph = [list(input()) for _ in range(N)]
result = ""
def check(x, y, s):
    lst = [graph[i][y:y+s] for i in range(x, x+s)]
    if len(set(k:=sum(lst, []))) == 1:
        return True, k[0]
    else:
        return False, k[0]

def qurd(x, y, s):
    global result
    if (r:=check(x,y,s))[0] or s == 1:
        result += str(r[1])
        return
    div = s // 2
    result += "("
    qurd(x,y,div)
    qurd(x,y+div,div)
    qurd(x+div,y,div)
    qurd(x+div,y+div,div)
    result +=")"

qurd(0, 0, N)
print(result)

---

회고

재귀 문제를 풀이한지 2일 정도 되었고 총 투자 시간은 6시간 정도 되는데, 어제까지만해도 이런 문제 풀이할 때 거의 2시간 정도 풀이 하였지만, 20분 안에 모든 코드를 구상하고 문제를 풀이하였다.
이부분에서 발전이 있었다고 생각하며, 이제 트리 자료구조를 공부할 준비가 되었다고 생각한다.

살짝 고민했던 부분은 이때까지 들어오는 값의 형태는 정수형이었지만, 이번엔 문자열이었다. 파이썬이라 크게 고민하지 않고 풀었던것도 한 몫 한 것 같다.

또한 이전보다 재귀 함수를 구현하는 형태도 조금 깔끔해진 것 같다. 다만 check함수에서 리턴값이 2개라 역할을 너무 많이 부여한것이 실책이라면 실책.