[백준] 2630번 색종이 만들기

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

2630번: 색종이 만들기

분할 정복 문제로, 재귀로 풀면 된다.

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> v;

int white = 0;
int blue = 0;

void divide(int startRow, int startCol, int endRow, int endCol) {
	//cout << startRow << "~" << endRow << "행 " << startCol << "~" << endCol << "열" << endl;
	int color = v[startRow][startCol];
	bool flag = true;
	for (int i = startRow; i <= endRow; i++) {
		for (int j = startCol; j <= endCol; j++) {
			if (v[i][j] != color) {
				flag = false;
				break;
			}
		}
		if(!flag)
			break;
	}
	if (!flag) {
		//cout << "한 덩어리로 안 됨" << endl;
		divide(startRow, startCol, startRow + (endRow - startRow) / 2, startCol + (endCol - startCol) / 2);
		divide(startRow, startCol + (endCol - startCol) / 2 + 1, startRow + (endRow - startRow) / 2, endCol);
		divide(startRow + (endRow - startRow) / 2 + 1, startCol, endRow, startCol + (endCol - startCol) / 2);
		divide(startRow + (endRow - startRow) / 2 + 1, startCol + (endCol - startCol) / 2 + 1, endRow, endCol);
	}
	else {
		if (v[startRow][startCol] == 0) {
			//cout << "흰 종이" << endl;
			white++;
		}
		else {
			//cout << "파란 종이" << endl;
			blue++;
		}
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	v = vector<vector<int>>(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> v[i][j];
		}
	}
	divide(0, 0, n - 1, n - 1);
	cout << white << endl;
	cout << blue << endl;
	return 0;
}