[Beakjoon, C++] 2630번 : 색종이 만들기

백준 단계별 풀기에서 분할정복 첫번째 문제이다.
링크는 아래와 같다.

www.acmicpc.net/problem/2630

18258번: 큐 2

---

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

---

백준 2630번 입출력 예제 1

---

1. 분할정복 문제는 재귀함수를 활용하는 것이다. 문제를 직면했을 때, 그것을 쪼개갠 작은 문제들을 해결한다면 그 문제들의 해결이 곧 그 문제의 해결이라는 것이다.  아래의 그림을 보자. 이번 문제에서 큰 사각형으로 바라본다면 사각형 안에 파란색, 하얀색 두가지가 섞여 있을 것이다. 하지만, 다음과 같이 쪼개고 쪼개다 보면, 결국 한가지의 색만 가지는 사각형을 얻을 수 있을 것이다. 

Devide & Conquer의 예

2. 어떤식으로 재귀함수를 전개할 것인가. 

 함수의 기능은 배열전부가 하얀색이면 하얀색 카운트, 배열전부가 파란색이면 파란색 카운트, 그렇지 않다면, 사각형을 쪼개서 함수에 넣기.

 프로그래밍적으로, 함수func가 있다. func는 2중 for문으로 2차원 배열(NxN) index 전부를 읽어서, 읽은 값이 0이면 하얀색 count, 1이 N^2개이면 전부 파란색이라는 뜻이니까 파란색 count, 0과 N^2 사이값이면 파란색 하얀색 섞여 있는 것이니까 N/2해서 func(N/2)로 다시 func를 call 한다.  

---

 

#include<iostream>

using namespace std;

int paper[129][129];
int whitePaper = 0;
int bluePaper = 0;

void paperColorDecisionByDivdeConquer(int x, int y, int N) {
	int tempBlueCount = 0; // 
    //2중 for문으로 0인지 1인지 탐색
	for (int i = x; i < x + N; i++) {
		for (int j = y; j < y + N; j++) {
			if (paper[i][j]) {  //파란색일때
				tempBlueCount++;  // 파란색 개수 count
			}
		}
	}
	if (!tempBlueCount) whitePaper++; // 하얀색
	else if (tempBlueCount == N * N) bluePaper++; // 파란색
	else {   // 쪼갬
		paperColorDecisionByDivdeConquer(x, y, N / 2);  // 왼쪽 위 사각형
		paperColorDecisionByDivdeConquer(x, y + N / 2, N / 2); // 오른쪽 위 사각형
		paperColorDecisionByDivdeConquer(x + N / 2, y, N / 2); // 왼쪽 아래 사각형
		paperColorDecisionByDivdeConquer(x + N / 2, y + N / 2, N / 2); // 오른쪽 아래 사각형
	}
	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];
		}
	}
	paperColorDecisionByDivdeConquer(0, 0, n);

	cout << whitePaper << "\n";
	cout << bluePaper;
	return 0;
}

---

이상으로 분할정복 첫 번째 문제를 마치겠다.