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

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))

(+) 2년전에 C++로 풀이해둔 풀이도 있다. (백준 1992문제)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
void decompress(vector< vector<int> >&v,int y, int x, int size){

	if(size==1){
		cout<<v[y][x];
		return;
	}
	else{
	//사례: 전부 1이거나 0이면 분할 안해줘도됨  
		bool notsame=false;
		int Arr=v[y][x];
		for(int i=y;i<y+size;++i){
			bool brk=false;
			for(int j=x;j<x+size;++j){
				if(Arr!=v[i][j]){
					notsame=true;
					brk=true;
					break;
				}
			}
			if(brk)
				break;
		}
		if(!notsame){//전부 일치하므로 압축해제하지않고 출력 
			cout<<v[y][x];
		}
		else{
			//네 부분을 각각 순서대로 압축 해제한다.
			int half=size/2;
			cout<<"(";
			decompress(v,y,x,half);
			decompress(v,y,x+half,half);
			decompress(v,y+half,x,half);
			decompress(v,y+half,x+half,half); 
			cout<<")";
		}
	}
}
int main(){
	int size;
	cin>>size;
	vector< vector<int> > v(size, vector<int>(size));
	for(int i=0;i<size;i++){
		for(int j=0;j<size;j++){
			scanf("%1d", &v[i][j]);
		}
	}
	decompress(v,0,0,size);
	return 0;
}