[Algospot] QURDTREE

풀이

• x가 항상 부모노드가 되도록 트리를 생성한다

  • x는 편의상 숫자로 변환하였다 첫번째 x가 0 ... n번째 x는 (x의개수)-1 이다

• x가 나오면 x의 숫자에 해당하는 해당 인덱스 board 리스트에 넣고
  새로운 헤드를 만들어 재귀호출 한다.

• 해당 인덱스 board 리스트의 개수가 4개가 되는 상황을 탈출 조건으로 한다.

  예시 xxwwwbxwxwbbbwwxxxwwbbbwwwwbb

  • 첫번째 x는 0번 인덱스 board에 넣는다.
    0 : 1
  • 두번째 x는 1번 인덱스 board에 넣는다.
    0 : 1
    1 : 2
  • wwwb는 모두 2번 인덱스 board에 해당한다.
    0 : 1
    1 : 2
    2: wwwb -> 2번 인덱스 board가 다 찼으므로 return
  • 다음을 반복하다 보면 트리가 완성된다

• 보드를 가로 기준으로 뒤집었으므로 탐색은 3 ,4, 1, 2 순서로 해야한다.

import sys

testcase = int(sys.stdin.readline())

for t in range(testcase):
    qurdboard = list(map(str,sys.stdin.readline()))
    i = 0
    board = [[] for i in range(qurdboard.count("x")+1)]

    for z in range(len(qurdboard)):
        if qurdboard[z]=="x":
            i+=1
            qurdboard[z]=i

    def create_tree(index,q):   
        if q>=len(qurdboard) :
            return q
        
        for i in range(4):
            if q>=len(qurdboard) :
                break
            if qurdboard[q] in ["w","b"]:
                board[index].append(qurdboard[q])
                q+=1
            else :
                board[index].append(qurdboard[q])
                q = create_tree(qurdboard[q],q+1)

        return q
    
    def find_reverse_tree(index):
        for i in range(len(board[index])):
            if index == 0 :
                tmp = i
            else :tmp = (i+2)%4

            if board[index][tmp]=='\n':
                print("")
                return
            
            if board[index][tmp] in ["w","b"]:
                print(board[index][tmp],end="")
            else :
                print("x",end="")
                find_reverse_tree(board[index][tmp])
    
    create_tree(0,0)
    find_reverse_tree(0)