[백준 BOJ] 1992 : 쿼드 트리 (C++)

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

1992번: 쿼드트리

아이디어 흐름

1. 아이디어 구상

백준 1074번 Z 문제를 살펴본 후 이 문제를 접하여 분할정복 + 재귀를 이용하는 문제라는 것은 바로 직감이 왔다. 바킹독님 알고리즘 강의에서 본 풀이 순서를 그대로 따르려고 노력했다

1. 함수의 정의 : func(int y, int x, int n), 어떠한 조건에 따라 분할을 하게될지는 모르지만, 좌표를 나타내는 y, x 와 분할한 정사각형의 크기인 n을 인자로 넘기며 재귀함수가 동작할 것이라 쉽게 짐작할 수 있었다.
2. base condition : 어떻게 분할될지는 모르지만, 어쨋든 n == 1이 되면 더 이상 쪼갤 것이 없으므로 인덱스 출력 후 return 으로 함수를 끝내도록 base condition 처리

   // base condition
   if (n == 1) {
   	cout << arr[y][x];
   	return;
   }

   
   
3. 알고리즘
   • cur = arr[y][x]를 저장해둔 후 이중 for문을 돌며 cur와 arr가 다른 것이 나오게 되면 flag를 false 로 돌리고 반복문을 탈출

   // 이중 for문을 돌며, 반복문을 시작할 때와 다른 값이 나올 경우 반복문 탈출
   char cur = arr[y][x];
   bool flag = true;
   
   for (int i = y; i < y + n; i++) {
   	for (int j = x; j < x + n; j++) {
   		if (cur != arr[i][j]) {
   			flag = false;
   			break;
   		}
       }
       if (!flag) break;
   }

   
   
   • flag에 따라 return 혹은 4분할 진행 

   if (flag) cout << cur;	
   else {
   	cout << "(";
   	func(y, x, n / 2);
   	func(y, x + n / 2, n / 2);
   	func(y + n / 2, x, n / 2);
   	func(y + n / 2, x + n / 2, n / 2);
   	cout << ")";
   }

   
   

3. 코드

#include <iostream>
using namespace std;

char arr[65][65];
void func(int y, int x, int n) {
	// base condition
	if (n == 1) {
		cout << arr[y][x];
		return;
	}

	char cur = arr[y][x];
	bool flag = true;

	// 이중 for문을 돌며, 반복문을 시작할 때와 다른 값이 나올 경우 반복문 탈출
	for (int i = y; i < y + n; i++) {
		for (int j = x; j < x + n; j++) {
			if (cur != arr[i][j]) {
				flag = false;
				break;
			}
		}
		if (!flag) break;
	}
	
  	// flag에 따라 return 혹은 4분할 진행 
	if (flag) cout << cur;	
	else {
		cout << "(";
		func(y, x, n / 2);
		func(y, x + n / 2, n / 2);
		func(y + n / 2, x, n / 2);
		func(y + n / 2, x + n / 2, n / 2);
		cout << ")";
	}
}

int main() {
	int n;
	cin >> n;

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

	func(0, 0, n);
}



4. 아쉬운점

• 총 소요시간 : 1시간 7분
• 아이디어 구상 : 30분
• 코드 작성 및 디버깅 : 37분

DFS, BFS문제를 풀 때에 비해 배열 인덱스 실수라던가 구현실수는 더 적어 코드를 작성하고 디버깅하는 과정은 크게 오래걸리지 않았지만, 분할정복 문제를 처음 풀다보니 '언제 분할을 해주어야하는가'를 코드로 생각하기가 너무 어려웠던 것 같다.

'이중 for문을 반복한 결과 0과 1이 섞여있을 경우 4분할을 진행한다' 는 아이디어가 핵심인데 이 아이디어를 떠올리기까지 30분이 걸렸다.