알고스팟 쿼드 트리 뒤집기 (quadtree) 문제 파이썬으로 풀기

이미지를 압축하는 방식 중 하나인 쿼드 트리를 입력으로 받아 원 그림의 상하를 뒤집은 모습을 쿼드 트리로 출력하면 된다.

문제를 풀며 분할 정복이란 것에 한발짝 발을 딛는 듯한 느낌을 받았다. 

이 문제는 입력을 여러 조각으로 나누어 풀어야 하는데, 'x'+왼쪽 위+오른쪽 위+왼쪽 아래+오른쪽 아래로 나누고, 그거에 맞춰 상하로 바꾸어주어야 한다.

인터넷에서 그림을 이용하여 쉽고 빠르게 이해할 수 있는 글을 찾았는데,

https://gurumee92.tistory.com/153

알고스팟 문제 풀이 QUADTREE

바로 이 글이다. 

 

여기에 나온 내용을 보고 코드를 짰더니 한번에 정답이 떳다.

#quadtree
def quad(loctree, ind):
    let = loctree[ind]  # 인덱스 번째의 글자
    if let == 'w' or let == 'b':  # 상하 바꿔도 변함이 없음
        return let
    # let이 w나 b가 아닌 경우=let이 x일때
    ind += 1  # x가 나온 위치로부터 1칸 뒤
    a=quad(tree,ind)
    ind += len(a)  # 왼쪽 위가 차지하는 칸수 만큼 뒤
    b=quad(tree,ind)
    ind += len(b)  # 오른 위가 차지하는 칸수 만큼 뒤
    c=quad(tree,ind)
    ind += len(c)  # 왼쪽 아래가 차지하는 칸수 만큼 뒤
    d=quad(tree,ind)
    return 'x'+c+d+a+b
 
 
case = int(input())
for i in range(case):
    tree = input()
    print(quad(tree, 0))  # 인덱스=0

이렇게 코드를 짜고,

 

느낀점:

1. 

많은 사람이 이렇게 reverse를 이용해서, 파이썬으로 저걸 구현하려 했는데 잘 되지 않았다.

파이썬 실력은 언제쯤 늘게 되는걸까..

2. 분할 정복이란 용어 자체는 생소하지만, 작게 나눠서 풀고, 결과를 합치는건 재귀에서 많이 해본거라 익숙했다. 그저 내 실력만 문제인거지