BOJ1992 쿼드트리

문제

1992번: 쿼드트리

실버1

아이디어

• 👩

  분할 정복 난 진짜 잘 못푸나보다...그래도 3문제 정도 분할정복 문제를 겪다보니, 대충 어떤 구조로 이뤄졌는 지 알겠다..

  최종깊이까지 갔을 땐 마지막 값을 리턴하는 재귀함수로 만드는데, 반으로 분할 되서 재귀로 넘겨주는 느낌?

코드

import sys
sys.stdin = open('BOJ1992.txt')

N = int(input())

arr=[list(map(int,sys.stdin.readline().rstrip())) for _ in range(N)]
result = []

def find(r,c,n):
    if n == 1:
        print(arr[c][r],end="")
        return
    flag=True
    for i in range(c,c+n):
        if not flag:
            break
        for j in range(r,r+n):
            if arr[i][j] != arr[c][r]:
                flag = False
                break

    if flag:
        print(arr[c][r],end="")
    else:
        print('(',end="")
        find(r,c,n//2)
        find(r+n//2,c,n//2)
        find(r,c+n//2,n//2)
        find(r+n//2,c+n//2,n//2)
        print(')',end="")
find(0,0,N)