백준 1992 쿼드 트리 C++

백준 1992 쿼드 트리.

백준 1992번 "쿼드 트리" 문제의 자세한 내용은 글 하단의 문제 링크를 참고하세요.

1992번 문제에 주어지는 입력 및 예시

입력: 

8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

출력:

((110(0101))(0010)1(0001))

코드

백준 1992번 "쿼드 트리" 문제의 코드입니다.

1. 재귀- 바로 출력.

#include <bits/stdc++.h>
using namespace std;
char a[65][65];
void qt(int y,int x, int size){
	if(size==1){
		cout<<a[y][x];
		return;
	}
	for(int i=y;i<y+size;i++){
		for(int j=x;j<x+size;j++){
			if(a[y][x]!=a[i][j]){
				cout<<'(';
				qt(y,x,size/2); 
				qt(y,x+size/2,size/2);
				qt(y+size/2,x,size/2);
				qt(y+size/2,x+size/2,size/2);
				cout<<')';  
				return;
			}
		}
	}
	cout<<a[y][x];
	return;
}
int main() {
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n;
	string s;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>s;
		for(int j=0;j<n;j++)
			a[i][j]=s[j];
	}
	qt(0,0,n);
	return 0;
}

2. 재귀- 결과값 리턴

#include <bits/stdc++.h>
using namespace std;
char a[65][65];
string qt(int y,int x, int size){
	if(size==1) return string(1,a[y][x]); 
	char b=a[y][x];
	string result="";
	for(int i=y;i<y+size;i++){
		for(int j=x;j<x+size;j++){
			if(b!=a[i][j]){
				result+='(';
				result+=qt(y,x,size/2); 
				result+=qt(y,x+size/2,size/2);
				result+=qt(y+size/2,x,size/2);
				result+=qt(y+size/2,x+size/2,size/2);
				result+=')';  
				return result;
			}
		}
	}
	return string(1,a[y][x]);
}
int main() {
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n;
	string s;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>s;
		for(int j=0;j<n;j++)
			a[i][j]=s[j];
	}
	cout<<qt(0,0,n)<<"\n";
	return 0;
}

실행

위의 코드를 예제의 입력을 넣어 실행했을 때의 결과입니다.

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

1992번: 쿼드트리