[백준 BOJ_1992] 쿼드트리 Python 풀이

출처: 백준 온라인 저지

문제

풀이

우선 영상의 크기 n과 시작하는 좌표 (y, x)를 받는 quadtree함수를 만들어 주었습니다.

n이 1일때는 제일 작은 경우(기저사례) 이기 때문에 해당 좌표의 값을 반환해줍니다.

문제에서 힌트를 얻을 수 있듯이 영상을 좌측상단, 우측상단, 좌측하단, 우측하단으로 4등분하여 더이상 나눌 수 없을 때까지 재귀호출해주면 됩니다.

하지만 해당 부분이 같은 값으로 이루어져 있다면 더이상 쪼개지 않고 반환해주어야 하기 때문에 이중 for loop을 돌려 확인해주었습니다. 만약 모두 같은 값으로만 이루어져 있다면 역시 해당 좌표의 값을 반환해줍니다.

n을 반으로 나누어 준 뒤, 4등분한 영상의 시작좌표 또한 나눈 n값으로 아래의 그림과 같이 바꿔줍니다.

재귀호출한 네 부분들의 값을 처음과 끝 부분에 괄호”()”를 포함한 하나의 string으로 합해준 뒤 반환해줍니다.

코드

def quadtree(n, y, x):
    if n == 1: 
        return qt[y][x]
    check = True
    for i in range(y, y+n):
        if not check:
            break
        for j in range(x, x+n):
            if qt[y][x] != qt[i][j]:
                check = False
                break
    if check:
        return qt[y][x]
    new_n = n // 2
    ret = "(" + quadtree(new_n, y, x) + quadtree(new_n, y, x+new_n) + quadtree(new_n, y+new_n, x) + quadtree(new_n, y+new_n, x+new_n) + ")"
    return ret

C = int(input())
qt = [ list(input()) for _ in range(C)]
print(quadtree(C, 0, 0))