[Baekjoon, C++] 1992번 : 쿼드트리

도입

백준 단계별 풀기에서 분할정복 두 번째 문제이다.

백준 1992번 문제, 입력, 출력

---

백준 1992번 입출력 예제 1

---

풀이

1. 앞의 '색종이 만들기' 문제와 유사하다. 재귀함수를 활용한다. 정사각형을 4개씩 쪼개면서 재귀함수를 호출하는 방식은 같으나, 출력에서 '('와 ')'를 해주어야 하는데 어디서 해야할까? 4개씩 재귀를 호출하는 곳에서 시작에서 '('를 해주고 재귀를 마칠때 ')'를 출력해주면 된다.

 함수call의 특성에서 a라는 함수가 수행 되는 중 b라는 함수가 call이 되면 a 함수는 사라지는 것이 아니다. stack구조 처럼 생각하자. a함수 수행 중 b함수가 call이 되면 a함수는 stack에 push된다(대기한다). 그리고 b가 다 수행이 되면 a함수가 stack에서 pop되면서 이전의 수행지점을 찾아 그 이후부터 수행이 된다. 따라서, a함수가 사라지는 것이 아니다. 이점을 잘 활용하는 것이 재귀함수인데, '('와 ')'를 사용할때는 주어진 사각형이 모두 0 또는 모두 1이 아니라서 쪼개질 때 해준다. 

 

2. 이번에 진행하면서 '틀렸습니다'를 보았는데, 원인은 파악은 하였는데, 이유를 잘 모르겠다. 값을 받을 때, 이전 문제처럼 cin을 통해서 배열값을 받았다. 근데, 이것이 문제였다. cin.get()으로 받았는데 맞았다. cin.get()과 cin의 차이점에 대해서 알 필요가 있다. cin은 엔터가 나오면 입력종료로 간주하지만, cin.get()은 엔터도 입력받을 문자로 간주한다. 

---

코드

틀렸습니다

#include<iostream>

using namespace std;

int paper[64][64];

void quadTree(int x, int y, int N) {
	int blackCount = 0;
	for (int i = x; i < x + N; i++) {
		for (int j = y; j < y + N; j++) {
			if (paper[i][j]) {
				blackCount++;
			}
		}
	}
	if (!blackCount) cout << "0"; // 하얀색
	else if (blackCount == N * N) cout << "1"; // 검은색
	else {   // 쪼갬
		cout << "(";
		quadTree(x, y, N / 2);  // 왼쪽 위 사각형
		quadTree(x, y + N / 2, N / 2); // 오른쪽 위 사각형
		quadTree(x + N / 2, y, N / 2); // 왼쪽 아래 사각형
		quadTree(x + N / 2, y + N / 2, N / 2); // 오른쪽 아래 사각형
		cout << ")";
	}
	return;
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> paper[i][j];
		}
	}

	quadTree(0, 0, n);

	return 0;
}

반례

My: (0((((00(0001)(1000))000)0(000(0(0100)00))((00(0101)0)0((1100)(1100)00)((1000)000)))0(((0(1100)00)000)000)0)(000((000(0(1101)00))(00((1010)0(1011)0)0)0(((1100)(1000)00)000)))(00(00((000(0001))(00(1001)0)0((1000)000))0)0))
     
A:   (0((((00(0001)(1000))000)0(00(00(0010)0)(0(0100)00))((00(0101)0)0((1100)(1100)00)((1000)000)))0(((0(1100)00)000)000)0)(000((000(0(1101)00))(00((1010)0(1011)0)0)0(((1100)(1000)00)000)))(00(00((000(0001))(00(1001)0)0((1000)000))0)0))

---

 

#include<iostream>

using namespace std;

int paper[64][64];

void quadTree(int x, int y, int N) {
	int blackCount = 0;
	for (int i = x; i < x + N; i++) {
		for (int j = y; j < y + N; j++) {
			if (paper[i][j]) {
				blackCount++;
			}
		}
	}
	if (!blackCount) cout << "0"; // 하얀색
	else if (blackCount == N * N) cout << "1"; // 검은색
	else {   // 쪼갬=재귀
		cout << "("; // 쪼개면서 (로 열어준다.
		quadTree(x, y, N / 2);  // 왼쪽 위 사각형
		quadTree(x, y + N / 2, N / 2); // 오른쪽 위 사각형
		quadTree(x + N / 2, y, N / 2); // 왼쪽 아래 사각형
		quadTree(x + N / 2, y + N / 2, N / 2); // 오른쪽 아래 사각형
		cout << ")"; // 재귀가 끝나면 )로 닫아준다.
	}
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	char tmp;

	cin >> n;
	cin.get();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin.get(tmp);
			paper[i][j] = tmp - 48;
		}
		cin.get();
	}
	/*int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> paper[i][j];
		}
	}*/

	quadTree(0, 0, n);

	return 0;
}
  

---

마무리

이상으로 쿼드트리 문제를 마치겠다.