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

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

1992번: 쿼드트리

 

 

 

Python

해당 섹션의 병합 여부를 판단하여

불가능 하면 무조건 4등분하기

import sys
input = sys.stdin.readline

N = int(input())
arr = [list(input().rstrip()) for _ in range(N)]

def recur(r,c,size):
    global arr
    if size == 1:
        return arr[r][c]
    
    ans = arr[r][c]
    for i in range(r, r+size):
        for j in range(c, c+size):
            if ans != arr[i][j]:

                size //= 2

                leftTop = recur(r, c, size)
                rightTop = recur(r, c+size, size)
                leftBottom = recur(r+size, c, size)
                rightBottom = recur(r+size ,c+size, size)

                return "("+leftTop+rightTop+leftBottom+rightBottom+")"    
    return ans
    
    
print(recur(0, 0, N))

 

 

시간 초과

처음부터 4등분에 대해 각각 합칠 수 있는지 확인하는 식으로 진행하니 시간초과가 되었다

import sys
input = sys.stdin.readline

N = int(input())
arr = [list(input().rstrip()) for _ in range(N)]


def recur(r, c, n):
    global arr

    if n == 1:
        return arr[r][c]
    half = n//2

    leftTop = arr[r][c]
    for i in range(r, r+half):
        for j in range(c, c+half):
            if arr[i][j] != leftTop:
                leftTop = recur(r, c, half)
                break

    rightTop = arr[r][c+half]
    for i in range(r+half):
        for j in range(c+half, c+half*2):
            if arr[i][j] != rightTop:
                rightTop = recur(r, c+half, half)
                break

    leftBottom = arr[r+half][c]
    for i in range(r+half, r+half*2):
        for j in range(c, c+half):
            if arr[i][j] != leftBottom:
                leftBottom = recur(r+half, c, half)
                break

    rightBottom = arr[r+half][c+half]
    for i in range(r+half, r+half*2):
        for j in range(c+half, c+half*2):
            if arr[i][j] != rightBottom:
                rightBottom = recur(r+half, c+half, half)
                break
    return "("+leftTop+rightTop+leftBottom+rightBottom+")"


print(recur(0, 0, N))