[백준] 1992- 쿼드트리 (Python)

문제 출처 :

www.acmicpc.net/problem/1992

1992번: 쿼드트리

문제 풀이 :

• 앞서 푼 종만북의 쿼드트리 뒤집기와 매우 비슷하게 느껴졋지만 난이도는 더 낮다.
• 종만북의 문제처럼 가장 큰 단위에서 체크하며 조건에 맞는다면 (0 이나 1로 다 채워져있다면) 그대로 return 하고 조건에 맞지 않는다면 재귀로 왼쪽상단,오른쪽상단,왼쪽 하단, 오른쪽 하단을 나눠서 조건이 맞을때까지 찾아본다.
• 입력이 무조건 2^N이기때문에 idx나 간격을 찾기가 굉장히 편하다.

n=int(input())
maps = [[] for _ in range(n)]

for i in range(n):
    temp = input()
    for j in temp:
        maps[i].append(j)

def check_area(i,j,k):
    global n,maps
    range_val = n//(2**k)
    start_val = maps[i][j]
    for x in range(i,i+range_val):
        for y in range(j,j+range_val):
            if(start_val!=maps[x][y]):
                #print(i,j,k)
                return False, None

    return True, start_val


def quadtree(i,j,k):
    global maps,n

    condition , str_ = check_area(i,j,k)
    #print(i,j,k,condition,str_)
    if(condition):
        return str_
    k+=1
    temp = 2**k
    UL = quadtree(i,j,k)
    UR = quadtree(i,j+(n//temp),k)
    LL = quadtree(i+(n//temp),j,k)
    LR = quadtree(i+(n//temp),j+(n//temp),k)

    return '('+UL+UR+LL+LR +')'

print(quadtree(0,0,0))