1992번 : 쿼드트리 - Python

문제

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

풀이

탐색을 시작할 첫번째의 값이 데이터 값이 변하지 않는다면 압축할 수 있다. 즉 출력할 수 있다. ()는 분할되는 과정에서 분할됨을 나타낸다. 즉, 데이터의 구간들이 값이 같다면 출력하고, 다르다면 4분할 하면서 푼다.

코드

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def quad(array, x, y, n):

    key = array[y][x]
    
    for i in range(y,y+n):
        for j in range(x,x+n):
            if key!=array[i][j]:
                next = n//2
                print('(',end='')#나눠짐을 의미한다.
                quad(array,x+(next*0),y+(next*0),next) #2사분면
                quad(array,x+(next*1),y+(next*0),next) #1사분면
                quad(array,x+(next*0),y+(next*1),next) #3사분면
                quad(array,x+(next*1),y+(next*1),next) #4사분면
                print(')',end='')
                return
            
    print(key,end='')
    return

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

quad(array,0,0,n)