[Python] BOJ 1992 : 쿼드트리

요구사항 

1. 시간제한 2초
   1. 약 2 * 10^8번의 연산이 가능 N^2까지 가능
2. 메모리 제한 128MB 
   1. 128 * 10^6 바이트 저장 
   2. 정수 리스트가 10^7 개라면 280메모리를 사용.  충분함.
3. 흰 점을 나타내는 0과 검은 점을 나타내는 1로 이루어진 영상(2차원 배열)에서 쿼드 트리를 이용 해 이를 압축하여 표현하자.

설계

1. 색종이 문제와 유사하다. https://studyiwthme.tistory.com/148
2. 사 사분면으로 나눈다. 
3. 같은 color 인지 확인한 뒤 맞다면 return 
4. 아니라면 각 사분면에 맞게 나눈다. (자세한건 위 링크에서 먼저 색종이 문제를 풀고 오세요)
5. 분할 정복이 시작할 때, 괄호를 열고 끝날 때 닫자.

구현

import sys
input = lambda: sys.stdin.readline().rstrip()
N = int(input().split())
quadTree = [list(map(int, input().split())) for _ in range(N)]

def solution(x, y, N) :
  image = quadTree[x][y]
  for i in range(x, x+N) :
    for j in range(y, y+N) :
      if image != quadTree[i][j] :
        print('(', end='')
        solution(x,y,N//2)
        solution(x,y+N//2,N//2)
        solution(x+N//2,y,N//2)
        solution(x+N//2,y+N//2,N//2)
        print(')', end='')
        return     
  if image == 0 :
    print('0', end='')
  else :
    print('1', end='')
  

solution(0,0,N)