쿼드트리 (feat. 백준, 1992번)

쿼드트리
https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int arr[64][64];
void solution(register int x, register int y, register int n) {
	register int sum = 0;
	for (register int i = 0, j; i < n; ++i)
		for (j = 0; j < n; ++j)
			sum += arr[x + i][y + j];
	if (sum == 0)
		cout << "0";
	else if (sum == n * n)
		cout << "1";
	else
		cout << "(", solution(x, y, n / 2),  solution(x, y + n / 2, n / 2), solution(x + n / 2, y, n / 2), solution(x + n/ 2, y + n / 2, n / 2), cout << ")";
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N;
	char tmp;
	cin >> N;
	for (register int i = 0, j; i < N; ++i)
		for (j = 0; j < N; ++j)
			cin >> tmp, arr[i][j] = tmp - '0';
	solution(0, 0, N);
	return 0;
}
// *&)*@*

1. n * n 의 2차원 배열의 전체 합이 0 또는 n * n이 아니라면 '(' 문자를 출력하고 n / 2 * n / 2의 2차원 배열로 재귀를 수행합니다.
2. 재귀는 (x,y) (x, y+n/2), (x+n/2, y), (x+n/2, y+n/2) 순서대로 수행합니다.