[백준 1992번] 파이썬 - 쿼드트리

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

1992번: 쿼드트리

 

 

# 조건

• 흑백 영상을 압축하여 표현하는 데이터 구조 쿼드 트리
• 흰 점을 0, 검은 점을 1로 표현하는 2차원 배열
• 모두 0으로만 되어 있으면 압축 결과 '0'
• 모두 1로만 되어 있으면 압축 결과 '1'
• 섞여 있다면, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 -> 4개의 영상으로 나누어 압축
• 압축한 결과를 차례대로 괄호 안에 묶어서 표현
• 2^i 개를 하나로 압축 가능하며 하나로 압축 안되면 그 안의 세부적으로 2^j개를 표현하면 된다.

 

# 접근 방법

• 분할 정복을 이용하여 각 부분을 구해주면 된다.
• 2^n 개씩 체크해보며 모두 동일하지 않다면 세부적으로 들어가준다.
• 또한 재귀로 탐색을 시작할 때 '( '를 넣어주며 압축시켜준다.
• 반복이 끝났다면 -> 현재 크기의 탐색이 끝났다면 닫는 괄호 추가
• 최소 크기 n == 1이 된다면 탈출
• 또한 모두 동일한 숫자로 구성되어 있다면 -> 반복문이 정상 종료되었다면 해당 숫자로 압축

 

import sys  
sys.stdin = open('input.txt')  
  
# 시작 위치 x,y와 현재 압축 중인 크기  
def check(x,y,n):  
    global result, arr, cnt  
    pivot = arr[x][y]  
  
    if n == 1:  
        result.append(pivot)  
        return 0  
  
    # 영역을 나눠준다면 현재 영상 크기를 전부 순회할 필요 x  
    # 탈출하기 위한 변수    
    flag = False  
    # 현재 영상의 크기만큼 순회  
    for i in range(x, x+n):  
        for j in range(y, y+n):  
            if arr[i][j] != pivot:  
                cnt = 0  
                # 영상 크기를 n//2한 후 재귀해준다.  
                # 따라서 반복문을 n//2씩 건너뛰며 반복                
                for k in range(x, x+n, n//2):  
                    for l in range(y, y+n, n//2):  
                        # 4등분 탐색 시작시 여는 괄호 추가  
                        cnt += 1  
                        if cnt == 1:  
                            result.append('(')  
                        check(k,l,n//2)  
                        flag = True  
  
                if flag:  
  
                    break  
        if flag:  
            # 현재 탐색이 끝났다는 조건문이므로  
            # 닫는 괄호 추가            
            result.append(')')  
            break  
    else:  
        result.append(pivot)  
        # result.append(')')  
  
N = int(input())  
arr = [list(input()) for _ in range(N)]  
cnt = 0  
result = []  
check(0,0,N)  
for i in result:  
    print(i, end='')