[백준✨] 1992번 <쿼드트리> / Python 문제풀이 /

해답)

import sys

def input():
    return sys.stdin.readline()

N = int(input())

board = []
for _ in range(N):
    board.append(list(input()))

def isAllSame(s_r, s_c, n):
    chk = board[s_r][s_c]
    for i in range(n):
        for j in range(n):
            if board[s_r+i][s_c+j] != chk:
                return False
    return True

    
def do(s_r, s_c, n):
    if n == 1:
        return board[s_r][s_c]
    if isAllSame(s_r,s_c, n):
        return board[s_r][s_c]
    l_u = str(do(s_r, s_c, n//2)) 
    l_d = str(do(s_r + n//2, s_c, n//2))
    r_u = str(do(s_r, s_c + n//2, n//2))
    r_d = str(do(s_r + n//2, s_c + n//2, n//2))
    return "(" + str(l_u) + str(r_u) + str(l_d) + str(r_d) + ")"

print(do(0,0,N))

---

풀이)

전형적인 분할정복의 문제입니다.

 

1. 타일이 한 종류의 색깔로 돼있는지 검사합니다.

1-1. 만약 한 종류거나, 변의 길이가 1이라면, 그대로 리턴합니다.

1-2. 만약 한 종류가 아니라면, 4등분을 해서 재귀적으로 실행시키고, 가로안에 4부분을 각각 출력해줍니다.

 

* 분할하고 합칠 때, 순서에 유념해야 합니다.

 

 

 

 

 

* 위 문제의 저작권은 백준(https://www.acmicpc.net/) 에 있습니다.