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

문제

 

www.acmicpc.net/problem/1992

1992번: 쿼드트리

 

코드

n = int(input())

tree = [list(map(int,(input()))) for _ in range(n)]
print(tree)
result = []

def quad_tree(x,y,n):
    global result
    color = tree[x][y]

    for i in range(x, x+n):
        for j in range(y, y+n):
            if color != tree[i][j]: # 범위안에 한개라도 다른경우는 4분면으로 나눠서 다시 검색
                result.append("(") # 4분면으로 나눌때 괄호를 친다.
                quad_tree(x,y,n//2)
                quad_tree(x, y+n//2, n//2)
                quad_tree(x+n//2, y, n//2)
                quad_tree(x+n//2, y+n//2, n//2)
                result.append(")")
                return
    result.append(color) # 재귀로 안들어가고 for문이 전부 다 끝난 상태이기 때문에 범위안에 모든수가 같다고 볼 수 있다.

quad_tree(0,0,n)
print("".join(map(str,(result))))

 

코드설명

n에 영상의 크기가 주어지고 n^2만큼 크기의 범위에 0과 1로 이어져 있다. 0과 1이 섞여있다면 4분면으로 나눠 압축하여 출력한다. 압축할때 괄호로 묶어준다.

 

quad_tree 함수가 실행이 되면 x,y범위값을 검사해 범위안에 서로 다른값이 있을경우 4등분으로 나눠주고 괄호를 쳐준다. 만약 재귀함수로 안들어가고 for문이 끝난다면 범위안에 값이 전부 같은 값이기 때문에 result에 append 해준다.

 

모든 재귀호출이 끝난뒤에 join을 이용해 result를 출력해준다.