[Python] 쿼드트리 - 백준 (분할정복)

해당 글은 백준 1992번 '쿼드트리' 문제를 다룬다.

문제

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

 

설명

처음에는 nxn 행렬을 모두 탐색하다가, (0, 0)의 값과 다르다면 4개로 나누어서 재탐색하는 분할정복 알고리즘으로 해결하였다. 주의할 점은 if문에 return으로 4분할로 재귀 후 종료할 수 있도록 해야한다.

 

코드

n = int(input())
arr = [list(map(int, input())) for _ in range(n)]

def check(x, y, n):
    for i in range(x, x+n):
        for j in range(y, y+n):
            if arr[x][y] != arr[i][j]:
                print('(', end='')
                n //= 2
                check(x, y, n)
                check(x, y + n, n)
                check(x + n, y, n)
                check(x + n, y + n, n)
                print(')', end='')
                return
    if arr[x][y] == 1:
        print(1, end='')
    else:
        print(0, end='')
        
check(0, 0, n)