BOJ-1992 쿼드트리

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

문제 소개

쿼드 트리는 흑백 영상을 압축하여 표현하는 데이터 구조이다.

주어진 영상이 모두 0/1으로 되어 있으면 압축 결과는 0/1이 된다.

0과 1이 영상에 섞여 있다면 영상을 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래로 나누어 압축하게 되며 그 결과는 괄호로 묶어서 표현한다.

예를 들어, 아래 영상은 (0110)으로 표현된다.

01
10

문제 풀이

재귀를 통해서 풀이하였다.

함수 is_valid()는 주어진 영상이 0 또는 1만으로 이루어져 있는지 검사한다. 0으로만 이루어져 있다면 0을, 1로만 이루어져 있다면 1을 출력하고 True를 반환하며 0과 1이 섞여 있다면 False를 반환한다.

함수 recursive()는 영상을 압축한다. 주어진 영상에 대해 is_valid()로 검사하며, 0과 1이 섞여있다면 영상을 4등분하여 각각에 대해 재귀적으로 recursive()를 호출하게 된다.

recursive()는 재귀 호출 이전에 “(“을 출력하여 괄호를 연 후 4개의 하위 영상에 대한 압축이 끝난 후 “)”를 출력하여 괄호를 닫는다.

코드

from sys import stdin
input = lambda: stdin.readline().rstrip()


# 영상 검사 함수
def is_valid(arr, n):
    t = []
    for i in range(n):
        t += list(set(arr[i]))
    if set(t) == {'0'}:
        print(0, end='')
        return True
    elif set(t) == {'1'}:
        print(1, end='')
        return True
    else:
        return False


# 압축 함수
def recursive(arr, n):
    if not is_valid(arr, n):
        # 4등분
        s = [[] for _ in range(4)]
        for i in range(n // 2):
            s[0].append(arr[i][:n // 2])
            s[1].append(arr[i][n // 2:n])
        for i in range(n // 2, n):
            s[2].append(arr[i][:n // 2])
            s[3].append(arr[i][n // 2:n])

        # 괄호 열고 닫기
        print("(", end='')
        for i in range(4):
            recursive(s[i], n // 2)
        print(")", end='')


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

recursive(arr, n)