분할정복 - 백준 1992번 쿼드트리

www.acmicpc.net/problem/1992

1992번: 쿼드트리

IDEA 

이 전 문제와 달리 쿼드트리문제는 무조건 왼쪽위 > 오른쪽 위 > 왼쪽 아래 > 오른쪽 아래 순서를 지켜야한다. 

한 쿼터 영역(예를 들어 왼쪽 위)에 대해 이중 for문을 돌며 모두 같은 숫자가 $n^{2}$개만큼 나왔는지 확인해준다.

한 쿼터 영역(예를 들어 왼쪽 위)이 모두 다 0 혹은 1 이 아니라면 압축 즉 한 번 더 4분할을 해주어야한다. 

그렇기 떄문에 한 번 더 압축 해줄 때 전후로 '(' ')'를 출력해주자.

 

코드 

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

int arr[65][65];

void divide(int start_row, int start_col , int n ){
	int zero = 0, one = 0;
	for (int i = start_row; i < start_row + n; i++) {
		for (int j = start_col; j < start_col + n; j++) {
			arr[i][j] == 1 ? one++ : zero++;
		}
	}
	if (one == n * n ) //모두 한 색깔로 채워져있는 경우
	{
		printf("1");
		return;
	}
	else if (zero == n * n) {
		printf("0");
		return;
	}
	else {
		printf("(");
		divide(start_row, start_col, n / 2);
		divide(start_row, start_col + n / 2, n / 2);
		divide(start_row + n/2, start_col, n / 2);
		divide(start_row + n/2, start_col + n/2, n / 2);
		printf(")");
	}
}


int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%1d", &arr[i][j]);
		}
	}
	divide(0, 0, n); 
}