[알고리즘] 분할정복 - 백준 1992번 쿼드트리

import sys
N = int(sys.stdin.readline())
papers = [sys.stdin.readline() for _ in range(N)]
result = ''

def solution(x, y, n):
    color = papers[y][x]
    global result

    for i in range(y, y+n):
        for j in range(x, x+n):
            if color != papers[i][j]:
                result += '('
                solution(x, y, n//2)
                solution(x+n//2, y, n//2)
                solution(x, y+n//2, n//2)
                solution(x+n//2, y+n//2, n//2)
                result += ')'
                return

    if color == '0':
        result += '0'
    else:
        result += '1'
    
solution(0, 0, N)
print(result)

풀이과정

1. 문자열을 구해야하는 문제임으로 result 변수에 빈 문자열을 넣는다.
2. 쿼드트리의 순서는 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래이다. [x][y]의 경우, for문을 돌 때, x는 고정된 채로 y만 움직이기 때문에 쿼드 트리의 순서와 일치하지 않는다. 따라서 [y][[x]를 기준으로 문제를 풀어야 한다.
3. 재귀를 호출하는 순서도 쿼드트리와 일치시킨다.
4. 모든 숫자가 같은 경우에는 해당 숫자를 result에 붙여준다.