[C++] 분할 정복(Divide and Conquer)

분할 정복(Divide and Conquer)

말 그래도 문제를 분할과 정복으로 나눠서 해결하는 것을 말한다.

• 분할 단계에서는 주어진 문제를 여러 개의 부분 문제들로 나누는데, 문제가 작아질수록 풀기 쉬워지기 때문이다.
• 대체로 분할 정복은 재귀 호출을 사용한다.

 

문제

 

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

1992번: 쿼드트리

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

int board[64][64];

void f(int n, int x, int y)
{
	bool color = board[y][x];
	bool diff = false;
	for (int i = y; i < n + y; ++i) {
		for (int j = x; j < n + x; ++j)
			if (color != board[i][j]) {
				diff = true;
				break;
			}

		if (diff)
			break;
	}

	if (!diff) {
		cout << color;
		return;
	}
	cout << "(";
	f(n / 2, x, y);
	f(n / 2, x + n / 2, y);
	f(n / 2, x, y + n / 2);
	f(n / 2, x + n / 2, y + n / 2);
	cout << ")";
}

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			scanf("%1d", &board[i][j]);

	f(n, 0, 0);
}

 

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

1780번: 종이의 개수

#include <iostream>
using namespace std;

int board[2190][2190];
int ans[3];

void f(int n, int x, int y)
{
	if (n == 1) {
		ans[board[y][x] + 1]++;
		return;
	}

	int tmp = board[y][x];
	bool diff = false;
	for (int i = y; i < n + y; ++i) {
		for (int j = x; j < n + x; ++j)
			if (tmp != board[i][j]) {
				diff = true;
				break;
			}
		if (diff)
			break;
	}

	if (!diff) {
		ans[tmp + 1]++;
		return;
	}

	n /= 3;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			f(n, x + n * j, y + n * i);
}

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			scanf("%d", &board[i][j]);

	f(n, 0, 0);
	cout << ans[0] << "\n" << ans[1] << "\n" << ans[2];
}