[Week 1] QUADTREE self review - profitjean

[profitjean]

QUADTREE self review

• 파일명: PQR/QUADTREE/profitjean.py
• 수행시간: 52ms

1. 고민 과정

재귀함수를 어떻게 활용하면 좋을지 고민을 많이 했었습니다.
문제에 나온 예시들(xbwxwbbwb)을 보면서 분할의 규칙들을 찾으려했습니다.

2. 풀이 아이디어

x로 시작하면 이후 4분면 분할이 진행되고
4분면(왼쪽부터1,2,3,4) 기준으로 상하반전시 3,4,1,2 순으로 재배치된다는 것을 확인했습니다.
예시(xbwxwbbwb)처럼 4분면안에 또 4분면이 중첩된 구조들이 존재하므로
재배치시 재귀함수를 사용하면 되겠다고 판단했습니다.

3. 작성한 코드와 설명

def quadtree(location, idx):
    word = location[idx]
    if word == 'w' or word == 'b':
        return word
    idx = idx + 1
    a = quadtree(tree, idx)
    idx = idx + len(a)
    b = quadtree(tree, idx)
    idx = idx + len(b)
    c = quadtree(tree, idx)
    idx = idx + len(c)
    d = quadtree(tree, idx)
    return 'x'+c+d+a+b

case = int(input())
for _ in range(case):
    tree = input()
    print(quadtree(tree,0))

처음 시작 인덱스는 0으로 설정하고, 각 영역의 시작 인덱스 위치는 다음처럼 설정했습니다.

• x: 인덱스0
• 1분면: 이전인덱스 값 + 1
• 2분면: 1분면 길이 + 1
• 3분면 : 2분면 길이 + 1
• 4분면 : 3분면 길이 + 1