[백준/BOJ/종만북/알고스팟]#1922:쿼드트리/QUADTREE [분할정복/파이썬/python]

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

재귀와 분할정복(divide and conquer)을 이용하여 푼다.

#1992_쿼드트리
n=int(input())
graph=[list(map(int,input())) for i in range(n)]
res=""
def quad(y,x,n):
    global res
    arr=graph[y][x]
    notsame=False
    for i in range(y,y+n):
        brk=False
        for j in range(x,x+n):1
            if arr!=graph[i][j]:
                notsame=True
                brk=True
                break
        if brk==True:
            break
    if notsame==False:
        res+=str(graph[y][x])
    else:
        half = n // 2
        res+='('
        quad(y, x, half)
        quad(y, x + half, half)
        quad(y + half, x, half)
        quad(y + half, x + half, half)
        res+=')'
    
quad(0,0,n)

print(res)

 

 

종만북에서도 문자열을 이용한 쿼드트리가 나온다. 그리고 이를 reverse변환도 해주어야한다.

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

algospot.com :: QUADTREE

 

왼쪽위-오른쪽위-왼쪽아래-오른쪽아래 순서로 압축해제가 된다.

쪼개야하면 '('나 ')' 구분자 아니면 x표시를 한다.

그리고 쪼개지는 부분을 또 거기서부터 압축해제한다. https://gurumee92.tistory.com/153 이 블로그에 그림까지 친절하게 설명해있으니, 압축해제 쿼드트리가 이해안된다면 참고하기.

 

종만북의 코드는 C++을 이용해서 포인터를 이용하여 이동한다.

파이썬에선 포인터가 없고 그냥 편하게 graph에서 배열(리스트)처럼 포인터이동해도 되므로 이를 head로 두었다.

백준과 마찬가지로 재귀호출을 하는데 포인터를 그 앞의 사분면만큼(오른쪽위 차례면 앞순서인 왼쪽위)의 커서를 이동해서 시작위치를 바꾸어준다.

그리고 리턴값을 왼쪽아래-오른쪽아래-왼쪽위-왼쪽아래로 reverse하게 두면 쉽게 reverse된 쿼드트리를 출력할 수 있다.

#algospot_QUADTREE
  
def decompress(it,graph):#쿼드트리 압축 해제하는 재귀호출함수
    head=graph[it]
    it+=1
    if head=='w' or head=='b':
        return head
    
    upperleft=decompress(it,graph)
    it+=len(upperleft)
    upperright=decompress(it,graph)
    it+=len(upperright)
    lowerleft=decompress(it,graph)
    it+=len(lowerleft)
    lowerright=decompress(it,graph)
    
    return "x" + lowerleft + lowerright + upperleft + upperright

c=int(input())
for i in range(c):
    graph=str(input())
    print(decompress(0,graph))