문제

문제 링크 : https://www.acmicpc.net/problem/1992

풀이

재귀 함수를 활용한 분할 정복으로 푸는 문제이다.

영상이 0으로만 이루어져 있거나 1로만 이루어져 있는지 확인한다. 만약에 그렇다면 0이나 1을 출력한다. 만약 그렇지 않다면 우선 '('을 출력하고 영상을 4등분해서 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래로 나눠서 quadTree를 호출해준다. 4개의 호출이 끝나면 ')'을 출력해준다.

from sys import stdin

n = int(stdin.readline())
l = [[] for i in range(n)]

for i in range(n):
    l[i] = list(map(int,list(stdin.readline().rstrip())))

def quadTree(x,y,length):
    cnt = 0
    for i in range(x,x+length):
        for j in range(y, y+length):
            cnt += l[i][j]
    if cnt == 0:
        print(0,end='')
    elif cnt == length**2:
        print(1,end='')
    else:
        print("(",end='')
        quadTree(x,y,length//2)
        quadTree(x,y+length//2,length//2)
        quadTree(x+length//2,y,length//2)
        quadTree(x+length//2,y+length//2,length//2)
        print(")",end='')

quadTree(0,0,n)