백준 1992번: 쿼드트리

 

 

 

 

분할 정복 문제다.

재귀(순환 호출)을 사용해서 풀면된다.

 

 

 

비슷하지만 분할 정복의 개념 문제라고 볼 수 있는 기본적인 문제를 푼적이 있다.

 

https://gimmesome.tistory.com/59

백준 2630번: 색종이 만들기

위 문제는

단지 0이나 1로 꽉차있는 사각형의 수를 각각 세는 것이기 때문에 재귀 순서가 상관이 없었다.

그러나 이 문제는 왼쪽 위를 기준으로 시계방향으로 도는 출력 순서를 원칙으로 하므로 재귀순서 또한 그걸 따라야한다.

또한, 위 문제는 숫자 사이에 공백을 두고 입력 받기 때문에 map으로 입력받는 것이 가능했으나

이 문제는 연속된 숫자로 입력을 받기에 string을 써서 입력을 받고 그걸 int로 만들어 array에 넣어야 한다.

 

 

 

 

 

중요 포인트

1. 0이나 1의 수를 각각 세어서 둘중 하나라도 사각형의 넓이와 같지 않으면 재귀(순환 호출) 한다.
2. 재귀(순환 호출)가 일어나기 전과 후에 '('와 ')'를 출력하면 된다.
3. 출력 순서는 왼쪽 위를 기준으로 시계방향이다.

 

#include <iostream>
#include <cstring> //memset
#include <string>
using namespace std;

int arr[65][65];	// 2의 7승이 최대라서 +1한거

void div_conq(int y, int x, int n) {
	
	int cnt_white = 0;
	int cnt_black = 0;

	for (int i = y; i < y+n; i++) {
		for (int j = x; j < x+n; j++) {
			if (arr[i][j] == 0)
				cnt_white++;
			else
				cnt_black++;
		}
	}
	
	//전부 흰색일때
	if (cnt_white == n * n)
		cout << 0;

	//전부 파란색일때
	else if (cnt_black == n * n)
		cout << 1;

	else {
		cout << '(';
		div_conq(y, x, n / 2);	//왼쪽 위 사각형
		div_conq(y, x + n / 2, n / 2);	//오른쪽 위 사각형
		div_conq(y + n / 2, x, n / 2);	//왼쪽 아래 사각형
		div_conq(y + n / 2, x + n / 2, n/2);	//오른쪽 아래 사각형
		cout << ')';
	}
	return;
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	//cin 실행속도 향상

	int n; 
	cin >> n; 
	
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < n; j++) {
			arr[i][j] = s[j] - '0';	//s[j]가 char여서 같은 char형식의 '0'를 빼준 나머지로 함
		}
	}

	div_conq(0, 0, n);	//맨처음 사각형은 시작점이 (0,0), 크기는 n

	return 0;
}