[Python] 1992. 쿼드 트리

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

1992번: 쿼드트리

접근법

• 제일 좌상단 위치를 기준으로 n x n 크기를 비교해서, 사이에 다른 값이 있는지 여부를 확인
  • 존재한다면 n x n을 4등분으로 나눠서 재귀 호출
  • 존재하지 않다면 좌상단의 값을 출력

백준 사이트에 나와있는 예제를 나누면 오른쪽 사진과 같이 나눌 수 있다.

• 처음 8x8 input의 모든 입력이 같지 않기 때문에 주황색 선 기준으로 나눈다.
• 나눈 각 4개의 사분면에서 2,4분면은 각각 0과 1로 모든 입력이 같기 때문에 더이상 나누지 않는다.
    1분면과, 3분면은 연두색 선 기준으로 나눈다.
• 같은 맥락으로 3분면의 1분면을 다시 파란색 선 기준으로 나눈다.

import sys
input = sys.stdin.readline

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

def quad_tree(cur_x, cur_y, num):
    cur = arr[cur_x][cur_y]
    for i in range(cur_x, cur_x + num):
        for j in range(cur_y, cur_y + num):
            if cur != arr[i][j]:
                print("(", end="")
                quad_tree(cur_x, cur_y, num//2)
                quad_tree(cur_x,cur_y + num//2, num//2 )
                quad_tree(cur_x + num//2, cur_y, num//2)
                quad_tree(cur_x + num//2, cur_y + num//2, num//2)
                print(")", end="")
                return
    if cur == '0': #arr을 input으로 받지 않았기 때문에 char 비교
        print("0", end="")
        return
    if cur == '1':
        print("1", end="")

quad_tree(0, 0, n)

 

 

사용된 알고리즘

분할정복, 재귀