[백준/파이썬] 1992번 쿼드트리 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1992번 쿼드트리
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

흑백 영상 배열을 쿼드트리 형식으로 압축해 출력하는 문제입니다.

코드

import sys

sys.setrecursionlimit(100_000)

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

def encode(rs, cs, size):
    x = image[rs][cs]
    
    if size < 2: return x
    
    for i in range(rs, rs + size):
        for j in range(cs, cs + size):
            if x != image[i][j]:
                x = '2'
                break
        if x == '2': break
    
    if int(x) < 2: return x
    
    return '(' +\
           encode(rs, cs, size//2) +\
           encode(rs, cs + size//2, size//2) +\
           encode(rs + size//2, cs, size//2) +\
           encode(rs + size//2, cs + size//2, size//2) +\
           ')'
    
print(encode(0,0,n))

설명

현재 영역이 전부 같은 값이면 그 값(0 또는 1)을 반환하고, 다르면 4분할해서 각 영역 결과를 괄호로 감싸 이어 붙입니다.

이 재귀 결과가 쿼드트리 압축 문자열입니다.

---

• 백준 문제풀이 전체 목록 보기

---