분할 정복 (쿼드 트리)

백준 1992 

 

import sys

N = int(sys.stdin.readline())

Narr = []

for i in range(N) :

    Narr.append(list(map(int,sys.stdin.readline().strip())))

def DFS(x,y,size) :

    global answerarr

    color = Narr[x][y]

    for i in range(x,x+size) :

        for j in range(y,y+size) :

            if Narr[i][j] != color:

                print("(",end= "")

                DFS(x,y,size//2)

                DFS(x,y+size//2,size//2)

                DFS(x+size//2,y,size//2)

                DFS(x+size//2,y+size//2,size//2)

                print(")",end= "")

                return

    if color == 0 :

        print("0", end= "")

        return

    else:

        print("1", end= "")

        return

DFS(0,0,N)

 

 

사실상 DFS랑 유사하다.

 

1. 처음 색깔을 COLOR에 저장

2. ARRAY를 처음부트 훑으면서, COLOR와 다른게 있다면 DFS처럼 범위를 분할하여 재탐색

3. 모든 색이 같다면 , 그때 RETURN . 

 

이 형태를 기억하자.