[종만북] 쿼드 트리 뒤집기(QUADTREE) (Python)

문제 출처 :

algospot.com/judge/problem/read/QUADTREE

algospot.com :: QUADTREE

문제 풀이:

• 종만북을 읽으면서 풀었기 때문에 문제를 푸는 시점부터 분할-정복 으로 풀어야 한다는 것을 인지하고 풀었다.
• 분할-정복 문제이므로 두 가지를 먼저 고민해야 했다.
  
  1.  어떻게 문제를 분할할 것인가? 
  2.  값을 리턴하는 순간들은 무엇인가?

1. 어떻게 문제를 분할 할 것인가?

처음 입출력과 문제의 답을 고려했을 때 막히는 부분은 2가지 였다.

• 입력되는 값에서 x를 기준으로 1개의 쿼드트리를 나누는 법 
  x를 기준으로 세부 쿼드트리들을 나눠야 하는데 매번 같은 길이를 가지는 것이 아니다. 때문에 "필요한 만큼만 가져다가 쓸 수 있도록" 해야한다.
• 가장 작은 단위의 문제를 확인해보자. 즉 2x2 크기의 쿼드트리를 뒤집는 법에 대해서 보았을때
  1 2  의 쿼드트리가 3 4 이면 된다. 즉 재귀로 짜면서 1 3번을 바꿔주고 2 4번을 바꿔주면 된다.
  3 4                     1 2

2. 값을 리턴 하는 순간들은 무엇인가?

책에서는 보통 기저사례라고 부르는데 이 값들은 압축열에서 x가 아닌 b 나 w인 경우이다. 그런경우에는 그냥 바로 리턴해주면 된다.

 

실제로 제일 어려웠던 부분은 x를 기준으로 필요한 만큼만 가져다가 쓰도록 만드는 부분이였던 것 같다.

 

c=int(input())

idx =0

def reverse_quadtree(quadtree):
    global idx
    head = quadtree[idx]
    idx+=1
    if(head=='b' or head=='w'):
        return head
    upperLeft = reverse_quadtree(quadtree)
    upperRight =reverse_quadtree(quadtree)
    lowerLeft = reverse_quadtree(quadtree)
    lowerRight = reverse_quadtree(quadtree)

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

for test_case in range(c):
    quadtree = input()
    quadtree = reverse_quadtree(quadtree)
    idx=0
    print(quadtree)