백준 1992번 쿼드트리 (Python)

 진작에 알고리즘 공부 좀 열심히 좀 할걸! 

오늘도 반성반성...

문제

 모두 0이나 1로 되어있으면 압축 결과는 0이나 1, 0과 1이 섞여 있으면 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 된다. 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다.

NXN 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

입력

  첫째 줄에는 영상의 크기를 나타내는 숫자 N이 주어짐. N은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진. 두 번째 줄부터는 길이 N의 문자열이 N개 들어옴. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타냄.

출력

 

영상을 압축한 결과를 출력해라.

풀이

 다양한 풀이 방법이 있겠지만 나는 보자마자 재귀함수로 풀어야겠다는 생각이 들었다.

X = int(input())
mat = [input() for _ in range(n)]
 
def quad(x1, y1, x2, y2, n) :
    
    if n == 1 :
        return mat[y1][x1]
 
    a = n // 2
    
    # 4등분으로 분할    
    r1 = quad(x1, y1, x1+a, y1+a, a)
    r2 = quad(x1+a,y1, x1+n, y1+a, a)
    r3 = quad(x1, y1+a, x1+a, y1+n, a)
    r4 = quad(x1+a, y1+a, x1+n, y1+n, a)
    
    # 모두 같은 값일 경우 하나만 출력
    if r1==r2==r3==r4 and len(r1) == 1 :
        return r1
 
    return "(" + r1 + r2 + r3 + r4 + ")"
 
 
print(quad(0,0,X,X,X))

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