백준 1992 쿼드트리 - 파이썬

문제.

 

 

풀이.

저번에 풀었던 색종이접기와 매우 유사하다.

똑같이 분할정복 알고리즘을 이용하여 쿼드트리 방식으로 나눠준다.

0 또는 1 하나로만 이루어지지 않았다면 괄호를 추가하고 분할을 하면 된다.

 

소스코드.

import sys

def div_con(x, y, n):
    global compression, paper
    color = paper[x][y]
    check = 0
    for i in range(x, x+n):
        if check != 0:
            break
        for j in range(y, y+n):
            if color != paper[i][j]:
                compression += '('  # 0, 1 하나로만 이루어지지 않았으면 '(' 추가
                div_con(x, y, n//2)  # 2사분면
                div_con(x, y+(n//2), n//2) # 1사분면
                div_con(x+(n//2), y , n // 2 )  # 3사분면
                div_con(x+(n//2), y+(n//2), n//2)       # 4사분면
                check = 1
                compression += ')'  # 분할 끝나면 ')' 추갗
                break

    if check == 0 and color == '0':
        compression += '0'
    elif check == 0 and color == '1':
        compression += '1'

N = int(sys.stdin.readline())
compression = ''
paper = []
for i in range(N):
    p = sys.stdin.readline().strip()
    p = list(p)
    paper.append(p)


div_con(0, 0, N)
print(compression)