📚 1992 - 쿼드트리

쿼드트리

이해

왼쪽 위 : 1번
오른쪽 위 : 2번
왼쪽 아래 : 3번
오른쪽 아래 : 4번

(0, 0) 좌표부터 시작한다.
전체 4등분을 해서 1번부터 확인한다.

• 그 구간 전체가 모두 1로만 되어 있으면 압축 결과 1 을 출력
• 그 구간 전체가 모두 0로만 되어 있으면 압축 결과 0을 출력
• 만약 둘 다, 아니고 섞여 있다면 (를 출력한뒤 재귀 호출을 한다.

재귀 호출할 때, 현재 해당 공간 크기에서 //2를 해준다. 이를 d라고 했을 때 해당 공간 4분면으로

(d, x, y)
(d, x + d, y)
(d, x, y + d)
(d, x + d, y + d)

나누어준다. (재귀 호출하여 해당 공간 결과를 구한다.)

소스

import sys

read = sys.stdin.readline
n = int(read())

arr = []

for _ in range(n):
    arr.append(list(map(int, read().strip())))


def quad_tree(c_size, x, y):
    if c_size == 1:
        print(arr[x][y], end="")
        return

    check = False

    for i in range(x, x + c_size):
        for j in range(y, y + c_size):
            if arr[i][j] != arr[x][y]:
                check = True
                break
        if check:
            break

    if not check:
        print(arr[x][y], end="")
    else:
        c_size //= 2

        print("(", end="")
        quad_tree(c_size, x, y)
        quad_tree(c_size, x, y + c_size)
        quad_tree(c_size, x + c_size, y)
        quad_tree(c_size, x + c_size, y + c_size)
        print(")", end="")


quad_tree(n, 0, 0)

# 참고 : https://dojinkimm.github.io/problem_solving/2020/01/08/boj-1992_quadtree.html

채점 결과

참고 : https://dojinkimm.github.io/problem_solving/2020/01/08/boj-1992_quadtree.html