[종만북] 분할정복 - 쿼드트리 QUADTREE

---

문제

https://www.algospot.com/judge/problem/read/QUADTREE

algospot.com :: QUADTREE

---

문제 분석 및 알고리즘 설계

• "x"라고 표현된 곳은 4분면으로 표현된다.
  • 4분면: 왼쪽 위(lt), 오른쪽 위(rt), 왼쪽 아래(lb), 오른쪽 아래(rb)
• 상하반전을 하면 다음과 같이 변한다. x + 왼쪽 아래(lb), 오른쪽 아래(rb), 왼쪽 위(lt), 오른쪽 위(rt)
• 단, 상하 반전 시 가장 안쪽부터 바깥쪽까지 적용해야 한다.

---

나의 풀이

import sys
sys.stdin = open('./input.txt', 'r')


def solve(s, idx):
    # 문자열을 모두 순회
    if idx == len(s):
        return ""

    c = s[idx]
    if c == 'b':
        return 'b'
    if c == 'w':
        return 'w'

    # x이면, 내부 트리를 상하 반전 후 반환
    idx += 1
    lt = solve(s, idx)
    idx += len(lt)
    rt = solve(s, idx)
    idx += len(rt)
    lb = solve(s, idx)
    idx += len(lb)
    rb = solve(s, idx)
    return f'x{lb}{rb}{lt}{rt}'


T = int(input())
for _ in range(T):
    print(solve(input(), 0))

---

해설

• 처음에는 단순히 데이터의 압축을 풀고, 이를 상하 반전 후 다시 압축하는 방식을 떠올렸다.
• 구현 중 어려움을 겪어 책과 다른 블로그를 찾아봤고, 압축된 상태에서 상하반전을 수행하는 새로운 방식을 알아냈다.
• 아직까지 분할 정복에 대한 이해가 부족하고, 관련 문제를 접근하는 데 시간이 오래 걸린다.

참고

https://gurumee92.tistory.com/153

---