[python] algospot QuadTree 문제풀이

문제

대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다.

쿼드 트리로 압축된 흑백 그림이 주어졌을 때, 이 그림을 상하로 뒤집은 그림 을 쿼드 트리 압축해서 출력하는 프로그램을 작성하세요.

-> 문제 링크 : https://algospot.com/judge/problem/read/QUADTREE

algospot.com :: QUADTREE

 

문제풀이

문제의 조건을 보면 원본 그림의 크기가 2^20 x 2^20이라는 것을 알 수 있다.

수가 굉장히 크기 떄문에 원본 그림을 복원해서 뒤집은 뒤 압축하는 방법은 불가능 하다.

 

우선 QuadTree 압축 방법을 자세히 살펴보면 문자 x 뒤에는 무조건 4개의 블록이 나온다는 것을 알 수 있다.

xbwxwbbwb도 x(b)(w)(xwbbw)(b)로 생각할 수 있다.

원본 블록이 네개로 분해된다면 분해된 블록을 각각 처리하면 원본 블록을 처리하는 것과 같은 결과를 낸다.

즉 각각은 독립적인 다른 영역에 해당되고, 서로 간섭하지 않는다. 

x를 만날 때 마다 뒤에 오는 문자열을 네개의 조각으로 나눠주고 각각을 처리하는 코드를 짜주면 된다.

 

1,2,3,4,                                                                                                   e,f,g,h

5,6,7,8                                                                                                    a,b,c,d

a,b,c,d                                                                                                    5,6,7,8

e,f,g,h  라는 블록이 있을 때 이를 상하로 뒤집는 결과는              1,2,3,4  가 된다.

 

이 과정을 블록 단위에서 생각해보면  

[ 1,2 ]     |    [ 3,4 ]                             [ a,b ]   |   [ c,d ]                                      [ e,f ]   |   [ g,h ] 

[ 5,6 ]     |    [ 7,8 ]                             [ e,f ]    |   [ g,h ]                                      [ a,b]   |   [ c,d ]

ㅡㅡㅡㅡㅡㅡㅡㅡ                            ㅡㅡㅡㅡㅡㅡㅡㅡ                                  ㅡㅡㅡㅡㅡㅡㅡㅡ

[ a,b ]     |    [ c,d ]              ==>       [ 1,2 ]   |   [ 3,4 ]                    ==>           [ 5,6 ]   |   [ 7,8 ]

[ e,f  ]     |    [ g,h ]                             [ 5,6 ]   |   [ 7,8 ]                                      [ 1,2 ]   |   [ 3,4 ]

 

4x4 블록에서 4개로 분할되어 위에 두 블록과 밑에 두 블록의 위치가 바뀌고, 

2x2 블록에서 4개로 분할되어 위에 두 블록과 밑에 두 블록의 위치가 바뀌는 과정을 거치면 상하 반전이 되는 것을 확인할 수 있다.

8x8 블록을 뒤집으면 8x8, 4x4, 2x2 에서 블록들의 위치를 바꿔주면 된다.

 

즉, NxN 블록이 들어온다면 log2(N)번 위에 두 블록과 밑에 두 블록의 위치가 바뀌는 과정이 반복되면 상하 반전이 된다.

 

위의 예제에서 4x4 블록이 분할되는 곳을 레벨1, 2x2블록이 분할되는 곳을 레벨2라고 해보자.

같은 레벨에 있는 블록간에는 간섭이 없기에 같은 레벨에 있는 블록간의 위치를 바꾸어도 블록 안에 담겨 있는 압축된 문자열에는 변화고 위치만 변동된다. 레벨1에서의 블록의 위치를 바꿔도 그 안에 담겨 있는 블록들은 변동이 없는 것을 볼 수 있다.

 

이 점을 이용하면 압축된 문자열을 풀지 않고 위치만 조정하여 상하반전된 결과를 낼 수 있다는 사실을 알 수 있다.

 

이를 코드로 변환하면 현재 재귀에서 네개의 블록으로 나눈 뒤 문자열의 위치만 조정해주면 된다.

it 변수 하나를 이용해 이동한다. it가 접근한 문자가 'x'면 뒤에 블록이 4개가 있다는 의미니까 재귀를 4번 불러준다.

만약 문자가 'b'나 'w'이면 그 블록은 하나의 색으로 통일된 블록을 의미하므로 해당 글자를 리턴한다.

 

압축된 문자열에서 블록이 적히는 순서는 좌측상단, 우측상단, 좌측하단, 우측하단 순서로 일정하기에

일정한 규칙을 만들면 문자열을 지정하는 변수 하나로 문제를 해결할 수 있다.

 

x(b)(w)(xwbbw)(b)을 예로 들어보자

it가 'x'를 가리키면 재귀를 4번 부른다. 첫번째 재귀에서는 'b'이므로 바로 리턴하고,

두번째 재귀에서는 'w'이므로 바로 리턴한다. 

세번째 재귀에서는 'x'이므로 또다시 4개의 재귀를 호출한다. 이 4개의 재귀가 모두 돌아지면 it는 계속 이동하고,

세번째 재귀가 끝나는 시점에는 it가 마지막 b에 위치해 있게 된다.

 

 

코드

import sys

N = int(sys.stdin.readline().rstrip())


def reverse() :
    global it

    head = string[it]
    it += 1

    if head == 'b' or head == 'w' :
        return head

    upperLeft = reverse()
    upperRight = reverse()
    lowerLeft = reverse()
    lowerRight = reverse()

    return "x" + lowerLeft + lowerRight + upperLeft + upperRight

for _ in range(N) :

    string = sys.stdin.readline().rstrip()
    it = 0
    print( reverse() )

 

초기 접근 방식과 오답의 원인

문제를 처음 접했을 때는 문제를 4개의 부분문제로 분할해야겠다는 생각은 했지만 그 후에 어떻게 처리해야할 지 감이 안잡혔다.

상단의 블록과 하단의 블록을 바꾸는 과정을 재귀적으로 생각하면 상하반전이 일어난다는 데에는 미처 생각이 닿지 않았다.

또한 문자열 접근을 it 변수 하나로만 이용한다는 생각을 못했고, 많은 입력을 집어넣다보니 문제가 너무 복잡해졌다.

 

분할되는 문제가 각각 독립적이고 순서가 있기에(?) it 변수 하나를 이용해 순서대로 처리할 수 있다는 점이 새로웠다.

 

 

코드에 잘못된 부분이나 개선 사항이 있다면 댓글로 알려주시면 감사하겠습니다.