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

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

1992번: 쿼드트리

Problem

• 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.
• 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다.

조건

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

SOL

아래 그림과 같이,  왼쪽위, 오른쪽 위, 왼쪽아래, 오른쪽 아래 순서대로 check를 진행한다. 만약, 안의 구성이 "1" 이나 "0"으로만 이루어져 있으면, 그걸 출력하면 된다.

하지만, 1과 0이 섞여 있을 때는, 또 나눠야한다. 필요한 과정이 뭐가 있는지 생각해보면 아래와 같다.

• 1 또는 0으로만 이루어져 있는지 확인을 해야한다.
• 1 또는 0으로만 이루어져 있지 않다면, "("을 앞에 적고, 이제 그 배열을 다시 4등분해서 왼쪽 위부터 chk 한다.
• 만약, N(길이)가 1이 된다면, 그걸 그대로 출력한다. (재귀의 탈출점)

#분할정복
import sys
input= sys.stdin.readline

N=int(input().rstrip())
board=[list(map(int,input().rstrip())) for _ in range(N)]

def chk_Quad(n,y,x):
    if n==1:
        print(board[y][x],end="")
        return
    flag = True
    for i in range(y,y+n):
        if not flag:
            break
        for j in range(x,x+n):
            if board[i][j] != board[y][x]:
                flag=False
                break
    if flag:
        print(board[y][x],end="")
    else:
        dec_n=n//2
        print("(",end="")
        chk_Quad(dec_n,y,x)
        chk_Quad(dec_n,y,x+dec_n)
        chk_Quad(dec_n,y+dec_n,x)
        chk_Quad(dec_n,y+dec_n,x+dec_n)
        print(")",end="")

chk_Quad(N,0,0)