[분할 정복] c++ 개념 및 1992 쿼드 트리 구현

목차

 

재귀함수를 하게되면 분할 정복을 만나게 된다.. 이참에 분할 정복을 정리하려고 한다.

 

분할 정복 정의

1. 분할

원래 문제를 분할하여 비슷한 유형의 더 작은 하위 문제로 분할이 가능할 때 까지 나눈다.

2. 정복

각 하위 문제를 재귀적으로 해결한다. 이때 기저 사례를 잘 만들어야 무한 루프에 빠지지 않는다.

3.결합

분할한 문제들을 통합하여 문제의 답을 얻는다.

 

 

장단점

분할 정복은 top-down 방식으로 재귀 호출의 장단점과 같다.

 

 

 

분할 정복 대표문제

1992 쿼드 트리

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

1992번: 쿼드트리

 

 

 

코드 구현

#include <iostream>
#include<stack>
#include<queue>
#include<algorithm>

using namespace std;

char board[64][64] = { 0 };

//분할 정복
string Searchs(int size, int s_x, int s_y) {
	//cout << s_x << " " << s_y << "\n";
	if (size == 1)  //기저 사례
		return string(1, board[s_y][s_x]);
	char b = board[s_y][s_x];
	string ret = "";
	bool flag = 0;
	for (int i = s_y; i < s_y + size; i++) {
		for (int j = s_x; j < s_x + size; j++) {
			if (b != board[i][j]) {
				ret += '(';
				ret+= Searchs(size / 2, s_x, s_y);
				ret += Searchs(size / 2, s_x + size / 2, s_y);
				ret += Searchs(size / 2, s_x, s_y + size / 2);
				ret += Searchs(size / 2, s_x + size / 2, s_y + size / 2);
				ret += ')';
				return ret;
			}
		}
	}
	return string(1, board[s_y][s_x]);  //값이 다 같을 경우 그대로 string return

}


int main()
{
	int n, i, j;
	string num;
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> num;
		for (j = 0; j < n; j++) {
			board[i][j] = num[j];
		}
	}
	cout << Searchs(n, 0, 0);
	return 0;
    
}

 

재귀에 대한 이해가 많이 필요하다...