[백준] 1992번 - 쿼드트리 Python 파이썬

📄 문제

❗️풀이

분할정복을 이용하면 된다
1. 영역 내 모든 숫자가 0 또는 1로 동일하다면 해당 값을 출력해준다.
2. 동일하지 않다면 영역을 4분면으로 쪼개서 각 영역에 대해서 0 또는 1로 동일한지 확인한다.
     - 2번 작업의 결과물을 출력할 때는 앞 뒤에 괄호'()'를 넣어주어야 한다.
3. 2번의 작업은 재귀함수로 진행이 가능하다.

✏️ 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N = int(input())
video = []
for _ in range(N):
    v = [int(x) for x in list(input().rstrip())]
    video.append(v)

def quadtree(n, vlist):
    s = 0
    for l in vlist:
        s += sum(l)
    
    if s == n**2:
        return '1'
    if s == 0:
        return '0'
    
    half = n//2
    temp = '('
    temp += quadtree(half,[l[:half] for l in vlist[:half]])
    temp += quadtree(half,[l[half:] for l in vlist[:half]])
    temp += quadtree(half,[l[:half] for l in vlist[half:]])
    temp += quadtree(half,[l[half:] for l in vlist[half:]])
    temp += ')'
    
    return temp

print(quadtree(N, video))

스스로 풀이 완료!