[python] 알고리즘 문제 해결 전략 1권 :: 쿼드 트리 뒤집기 (189p) 문제

7.2 문제 : 쿼드 트리 뒤집기 (문제 ID:QUADTREE, 난이도: 하)

대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다.

쿼드 트리는 2^N*2^N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다.

• 이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b가 됩니다.

• 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w가 됩니다.

• 모든 픽셀이 같은 색이 아니라면, 쿼드 트리는 이 그림을 가로 세로로 각각 2등분해 4개의 조각으로 쪼갠 뒤 각각을 쿼드 트리 압축합니다. 이때 전체 그림의 압축 결과는 x(왼쪽 위 부분의 압축 결과)(오른쪽 위 부분의 압축 결과)(왼쪽 아래부분의 압축 결과)(오른쪽 아래부분의 압축 결과)가 됩니다.

  쿼드 트리로 압축된 흑백 그림이 주어졌을 때, 이 그림을 상하로 뒤집은 그림을 쿼드 트리 압축해서 출력하는 프로그램을 작성하세요.

시간 및 메모리 제한

프로그램은 1초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다.

입력

첫 줄에 테스트 케이스의 개수 C(C<=50)가 주어집니다. 그 후 C줄에 하나씩 쿼드 트리로 압축한 그림이 주어집니다. 모든 문자열의 길이는 1,000 이하이며, 원본 그림의 크기는 2^(20)X2^(20)을 넘지 않습니다.

출력

각 테스트 케이스당 한 줄에 주어진 그림을 상하로 뒤집은 결과를 쿼드 트리 압축해서 출력합니다.

나의 답

testcase = int(input())
result = list()

def imageCom(img_str): #이미지 해석 후 arr로 만들기
    result_str = list()
    index = 0

    for i in range(0,4):
        if img_str[i]=="x":
            tmp_res,tmp_img =imageCom(img_str[i+1:]) 
            result_str.append(tmp_res)
            img_str=img_str[:i+1]+tmp_img
        else:
            result_str.append(img_str[i])
            index+=1
    img_str=img_str[4:]
    return result_str, img_str

def switching(arr):
    tmp = arr[0]
    arr[0]= arr[2]
    arr[2]=tmp

    tmp = arr[1]
    arr[1]= arr[3]
    arr[3]=tmp

    return arr

def upsideDown(img_arr): # 상하 뒤집기
    for i in range(0,4):
        if isinstance(img_arr[i],list):
            img_arr[i] = upsideDown(img_arr[i])
    return switching(img_arr)

def arrToString(array): # 결과 출력을 위해 문자열로 바꾸기
    tmp = str()
    for arr in array:
        if isinstance(arr,list):
            tmp+='x'+arrToString(arr)
        else:
            tmp+=str(arr)
    return tmp

for case in range(0,testcase):
    imageStr = input()
    if len(imageStr)==1:
        result.append(imageStr)
        continue

    tmp, nope = imageCom(imageStr[1:])
    result.append('x'+arrToString(upsideDown(tmp))) 

for res in result:
    print(res)

곧이 곧대로 바꾸는 방법을 썼으나 책과 다른 점은 전체 배열이 아닌 python list로 간단하게 표현하였다는 점이다.

시간 복잡도

최악의 경우 1000 길이의 문자열과 50개의 테스트 케이스가 존재하고, 2^(20)X2^(20)개의 모든 픽셀이 지그재그 흑백으로 존재할 때이다. 시간 복잡도는 50*20*1000*2 이고 간단히 나타내면 200000이다. 1억(10^8)보다 훨씬 낮은 수이므로 가능할 것으로 보인다.

직접 재보았을 때는 2^(5) 깊이에서 0.02s가 나왔다.

메모리

책에 있는 예제로 테스트 해보았을 때 0.03s 9176KB의 시간과 메모리가 소요되었다.