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

출처

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

문제

영상을 압축하여 표현할때 쓰는 구조인 쿼드트리이다.
정사각형을 기준으로 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 모두 0이면 0을, 1이면 1을 출력한다.다만 모두 0과 1이 아니면 표현하기 어려우므로 다시 4분면으로 나눠서 압축하게된다. 이 결과를 출력하는 함수를 만들면 된다.

접근방법

이 문제는 한번에 처리할 수 없으니 Divide and Conquer로 세부문제의 답을 구한후 합치면 된다. 출력부분을 고려하여 재귀를 사용하였다.

풀이

x, y 시작위치부터 사분면의 경계값인 n까지 검사하여 모두 0 또는 1인지 검사한 후, 아니라면 계속 경계값을 2로 나누어주며 사분면의 왼쪽 위를 각각 재귀호출 하여 풀었다.

import sys
n = int(sys.stdin.readline())
arr = [list(map(int, sys.stdin.readline().strip())) for _ in range(n)]

def recursion(x, y, n):
    check = arr[x][y]
    for i in range(x, x+n):
        for j in range(y, y+n):
            if arr[i][j] != check:
                print("(", end = '')
                recursion(x, y, n//2)
                recursion(x, y+n//2, n//2)
                recursion(x+n//2, y, n//2)
                recursion(x+n//2, y+n//2, n//2)
                print(")", end = '')
                return
    
    if check == 0:
        print("0", end = '')
        return
    else:
        print("1", end = '')
        return
        
recursion(0, 0, n)