[c++] 백준 1992, 쿼드트리

백준 1992

알고리즘 분류 : divide and conquer (분할 정복)

쿼드트리의 방법을 이용하여 4개의 영역을 압축한 결과를, 차례대로 괄호 안에 묶어서 표현하는 문제다. 재귀를 통해 해결한다.

살펴보는 영역 안에 check와 다른 문자가 존재하는 경우, 다음과 같이 재귀적으로 solve 함수를 호출한다. 순서대로 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래의 영역에 해당하며, size 또한 2로 나누어 넘겨준다.

solve(y,x,size/2);
solve(y,x+size/2,size/2);
solve(y+size/2,x,size/2);
solve(y+size/2,x+size/2,size/2);

만약 살펴보는 영역이 모두 같은 문자로 이루어져 있다면, check를 출력한다.

#include <iostream>
#include <string>

using namespace std;
string video[64];

void solve(int y,int x,int size){
	char check=video[y][x];
	
	for(int i=y; i<y+size; i++){
		for(int j=x; j<x+size; j++){
			if(check!=video[i][j]){ //영역에 check와 다른 문자가 존재하는 경우
				cout << '(';
				solve(y,x,size/2);
				solve(y,x+size/2,size/2);
				solve(y+size/2,x,size/2);
				solve(y+size/2,x+size/2,size/2);
				cout << ')';
				return;
			}
		}
	}
	cout << check;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N;
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> video[i];
	}
	solve(0,0,N);
}