no.2630 색종이 만들기

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;

int white = 0;
int blue = 0;
vector<vector<int>> square;


void divedePapaer(int row, int col, int size) {
	int first = square[row][col];
	bool isAlllSame = true;
	for (int i = row; i < row + size; i++) {
		for (int j = col; j < col + size; j++) {
			if (first != square[i][j]) {
				isAlllSame = false;
				break;
			}
		}
		if (!isAlllSame) {
			break;
		}
	}

	if (isAlllSame) {
		if (first == 0) {
			white++;
		}
		else {
			blue++;
		}
		return;
	}

	int half = size / 2;
	divedePapaer(row, col, half);
	divedePapaer(row, col + half, half);
	divedePapaer(row + half, col, half);
	divedePapaer(row + half, col + half, half);
}


int main()
{

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int N;
	cin >> N;
	square.assign(N, vector<int>(N));

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

	divedePapaer(0, 0, N);

	cout << white << "\n" << blue << "\n";

	return 0;

}

 

문제분석 

전체종이를 재귀적으로 네등분하며, 각 조각이 모두 같은색이 될때까지 잘라나가는 문제이다.

 

문제를 푸는 알고리즘은 이렇다 

 

1.맨 왼쪽의 좌표(0,0)과 현재 한 변의 사이즈를 전달

2.사이즈 x 사이즈 범위를 검사하여, 모두다 같은 색인지 검사 

3.하나라도 다른 색이 있을시, 가로/세로 반으로 나누어 4개의 구역으로 다시 검사 

 

핵심은 

1. 일정 구역이 전부 같은 색인지를 확인

2. 다르면 4분할

3.크기 1x1이거나 색이 전부 같은 구역이면, 해당 색종이 개수 1

4.분할 정복으로 전체를 처리 -> 끝

 

저번에 풀었던 Z보다 하위 개념?이라 쉽게 풀 수 있었다.