백준 쿼드트리 흑백 압축 (1992 실버 1) 재귀 분할정복

 

풀이: x1, y1, x2, y2로 가로 세로로 이분탐색을 해주면서 왼쪽 위, 오른쪽 위, 왼쪽 아래,  오른쪽 아래

순서대로 return을 해줍니다.

 

base condition: y1 < x1, y2 < x2, for문으로 확인 후 더 탐색할지 말지를 결정

for문을 체크 후 조건이 맞지 않는다면 더 분할하여 탐색하는 방법입니다

 

#include <iostream>

using namespace std;

int n;

char num[65][65] = {0,};
int arr[65][65] = {0,};

string qurdTree(int x1, int y1, int x2, int y2) {
	
	if(y1 < x1) return "";
	if(y2 < x2) return "";
	
	int oneCheck = 0;
	int zeroCheck = 0;
	
	for(int i = x1; i <= y1; i++) {
		for(int j = x2; j <= y2; j++) {
			if(1 == arr[i][j]) {
				oneCheck++;
			}
			else {
				zeroCheck++;
			}
		}
	}
	
	if(oneCheck == 0) {
		return "0";
	}
	else if(zeroCheck == 0) {
		return "1";
	}
	
	int mid1 = (x1 + y1) / 2;
	int mid2 = (x2 + y2) / 2;
	
	
	return "(" + qurdTree(x1, mid1, x2, mid2) + qurdTree(x1, mid1, mid2+1, y2) + qurdTree(mid1+1, y1, x2, mid2) + qurdTree(mid1+1, y1, mid2+1, y2) + ")";
}


int main() {	

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;

	
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			cin >> num[i][j];
		}
	}
	
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			arr[i][j] = num[i][j] - 48;
		}
	}
	
	cout << qurdTree(1,n, 1, n);

}