[BOJ][Python]1992번 풀이

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

1992번: 쿼드트리

import sys
ssr = sys.stdin.readline

def sol(r,c,l):
    global ans
    check = t[r][c]
    for i in range(r,r+l):
        for j in range(c,c+l):
            if t[i][j] != check:
                ans += '('
                sol(r,c,l//2)
                sol(r,c+l//2,l//2)
                sol(r+l//2,c,l//2)
                sol(r+l//2,c+l//2,l//2)
                ans += ')'
                return
    ans += check
    
n = int(ssr())
t = [list(ssr().rstrip()) for _ in range(n)]
ans=''
sol(0,0,n)
print(ans)

이것도 저번에 풀었던 색종이 문제와 본질은 같습니다. 재귀를 이용해서 영역을 나눠가면서 탐색을 하고 탐색 영역 내부의 데이터가 전부 같으면 그걸 숫자하나로 표현해서 데이터를 압축하는 방식의 하나라고 하는데 간단한 것 같으면서 좋은 방법이라고 생각이 되네요. 잘쓰면 독특한 형태의 영상처리 필터처럼도 쓸 수 있을 것 같네요. 다음에 한 번 쿼드트리 방식에 대해서 정리를 해보겠습니다.

 

문제 접근은 일단 기준값을 정하는 것 부터 시작합니다. 해당 영역내의 모든 값이 기준값과 같다면 숫자 하나로 표현할 수 있고 그 숫자는 기준값이 되겠네요. 또한 영역을 나눌 때(재귀 호출을 시작하기 전에) 원래는 한 영역이었다는 것을 표시하기 위해 괄호를 열어줍니다. 당연히 재귀 호출을 4영역까지 했다면 괄호를 닫아줘야겠죠. 물론 이건 영역을 나눌 때, 즉 기준값과 영역내의 모든 값이 같지는 않았다는 얘기가 되니까 다 같았을 때는 그냥 기준값만 써주면 됩니다.

손으로 직접 해보면 이런 느낌이 되겠죠. 저도 처음엔 무슨 소린가 싶었는데 직접 쓰면서 보니까 감이 바로 잡혔습니다. 가끔 머리로 고민할 때 자꾸 뭔가 엇나가는 것 같으면 손으로 쓰면서 해보는 것도 좋은 것 같아요.