[BOJ] 쿼드트리

코드

import sys
input = sys.stdin.readline

def solution(x, y, n):
    global ans
    color = graph[x][y]
    for i in range(x, x+n):
        for j in range(y, y+n):
            if graph[i][j] != color:
                ans += '('
                solution(x, y, n//2)
                solution(x, y+n//2, n//2)
                solution(x+n//2, y, n//2)
                solution(x+n//2, y+n//2, n//2)
                ans += ')'
                return
    ans += str(color)
        

n = int(input())
graph = [list(map(int, list(str(input().rstrip())))) for _ in range(n)]
ans = ''

solution(0,0,n)
print(ans)

풀이 방법

• 분할정복과 재귀를 활용하는 문제이다.
• solution(x, y, n) 함수를 정의하여, 현재 좌표 (x,y)를 최우측 상단으로 하는 n x n 크기의 정사각형이 모두 같은 색으로 이루어져 있는지 확인하고, 만약 하나라도 다른 색이 있으면 괄호를 연 다음 n x n 정사각형을 4개로 분할하여 재귀적으로 solution 함수를 호출한다. 호출한 함수들이 실행을 완료하면 caller 함수에서 괄호를 닫고 종료한다. 만약 모두 같은 색으로 이루어진 경우에는 그 색깔에 해당하는 숫자를 정답 문자열에 덧붙인다.