[C++] 백준 1992번 : 쿼드트리

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

1992번: 쿼드트리

---

 문제 풀이

이전 문제인 "BOJ 2630번 : 색종이 만들기"와 유사한 문제이다.

쿼드트리를 만들고 맞게 1과 0을 출력하면 된다.

다른 점은 입력받는 방법과 출력 시 '( )'을 맞춰서 출력해야 한다는 점이다.

입력은 공백이 없기 때문에 단순하게 cin으로 받을 수 없어서 string형으로 받고

str [i]가 char라서 아스키코드를 변환하는 방식으로 입력받는다.

출력 시 생성되는 괄호들은 4 분할이 될 때 출력해주면 된다.

 느낀 점

이전 문제와 유사해서 그렇게 어렵지 않은 문제였다. 쿼드트리가 무엇인지 어떻게 쓰이는지에 대해서 더 공부하면 될 것 같다.

 코드

#include <iostream>
#include <string>
using namespace std;

int map[65][65];
string str;
int n;

void div_conq(int x, int y, int n) {
	int cnt = 0;
	for (int i = x; i < x + n;i++) {
		for (int j = y; j < y + n;j++) {
			if (map[i][j]) cnt++;
		}
	}
	if (cnt == 0) cout << "0";
	else if (cnt == n * n) cout << "1";
	else {
		cout << "(";
		div_conq(x, y, n / 2);
		div_conq(x, y + n / 2, n / 2);
		div_conq(x + n / 2, y, n / 2);
		div_conq(x + n / 2, y + n / 2, n / 2);
		cout << ")";
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> str;
		for (int j = 0; j < n;j++) {
			map[i][j] = str[j] - '0';
;		}
	}
	div_conq(0, 0, n);
}