[BOJ]1992 쿼드트리

1. 문제

• 흑백 영상 → 압축 → 쿼드트리
  • 흰 점 : 0
  • 검은 점 : 1
  • 같은 점들의 몰려있으면 ‘0’ 혹은 ‘1’로 압축하여 출력
    ⇒ 영상을 압축한 결과?
• 입력 :
  1 | N (영상의 크기, 1 ≤ 2의_제곱수 ≤ 64)
이후| 길이 N의 문자열 N개
  
• 출력 :
  1| 영상 압축 결과

2. 풀이

[[1,1,1,1],
[0,1,1,1],        =>         LU | RU
[0,0,0,0],                  ---------- 
[1,1,0,0]                    LD | RD

• recursion을 통해 처리 → def quadTre(map)
  • 매개변수 map이 바로 압축 가능하다면
    • 1차원 list으로 변환하여 set로 압축했을 때 해당 set의 길이가 1이면 압축 가능
      → 압축 결과 ‘1’ / ‘0’을 반환
  • 만약 map의 길이가 2라면 == 더이상 압축되지 않는 최소 단위인 2*2 크기라면
    • 해당 map을 ‘(0101)’ 과 같이 string형태의 결과를 반환
  • 주어진 map의 상태에서 압축이 되지 않고, 2*2 보다 큰 이미지라면
    • 왼쪽위 | 오른쪽위 | 왼쪽아래 | 오른쪽아래 로 4등분하여 재귀적으로 quadTree호출 결과를 이용하여 결과 출력

3. 코드

import sys
input = sys.stdin.readline

N = int(input())
image = []

for n in range(N):
    image.append(list(input().rstrip()))

def quadTree(map):
    oneDim = []
    for row in map:
        oneDim += row

    if len(set(oneDim)) == 1 :
        return oneDim[0]

    if len(map) == 2:
        return '(' + ''.join(map[0]) + ''.join(map[1]) + ')'
    
    else:

        half = len(map) // 2

        up = map[:half]
        LU = [ x[:half] for x in up ] 
        RU = [ x[half:] for x in up ] 
        down = map[half:]
        LD = [ x[:half] for x in down ]
        RD = [ x[half:] for x in down ]

        return '(' + quadTree(LU) + quadTree(RU) + quadTree(LD) + quadTree(RD) + ')'

print(quadTree(image))

+α