[ALGOSPOT] 알고스팟 QUADTREE 쿼드 트리 뒤집기(Python)

www.algospot.com

[ALGOSPOT] 알고스팟 QUADTREE 쿼드 트리 뒤집기

(Python)

(글쓴날 : 2020.05.22)

 

---

* ALGOSPOT, 알고스팟 QUADTREE 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

알고스팟 QUADTREE 쿼드 트리 뒤집기

---

1) 문제

문제 링크 : https://www.algospot.com/judge/problem/read/QUADTREE

algospot.com :: QUADTREE

---

2) 풀이 과정

* 시간 복잡도 : O(n)

 

쿼드 트리로 압축된 흑백 그림이 주어질 때, 해당 그림을 상하로 뒤집힌 쿼드 트리 압축 형태로 바꾸는 문제입니다.

 

저의 경우, 분할 정복을 적용했으며, Python을 사용했습니다.

먼저, 그림의 4사분면 형태를 문자열 속에 추상적으로 대입하여, 문자열의 인덱스를 기준으로 각 분면을 나누었습니다.

(예를 들어, 1사분면을 leftUp, 2사분면을 rightUp, 3사분면을 leftDown, 4사분면을 rightDown이라는 문자열로 가정하였고, 각 분면 문자열의 시작 인덱스는 현재 인덱스 + 이전 분면 문자열의 길이입니다.)

그 후, 재귀 호출을 통해 각 분면에 해당하는 문자열을 구한 뒤, 상하가 뒤집힌 순서로 문자열을 재조합하여 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
 
def quadTree(index):
    if index >= len(picture):
        return ""
    
    if picture[index] == "w":
        return "w"
 
    if picture[index] == "b":
        return "b"
    
    leftUp = quadTree(index + 1)
    index += len(leftUp)
 
    rightUp = quadTree(index + 1)
    index += len(rightUp)
 
    leftDown = quadTree(index + 1)
    index += len(leftDown)
 
    rightDown = quadTree(index + 1)
    index += len(rightDown)
 
    return "x" + leftDown + rightDown + leftUp + rightUp
 
 
C = int(input())
 
for _ in range(C):
    picture = input().rstrip()
 
    ans = quadTree(0)
 
    print(ans)

---