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

알고리즘 분류: 분할 정복, 재귀

문제 링크: https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

 

 

 

 

【 풀이 】

 

1780번과 거의 유사한 분할, 정복 문제이다.

https://baehoon.tistory.com/62

[백준] 1780번: 종이의 개수 [C++]

 

 

• 범위를 정한다. (반복시 범위를 2로 나눈다.)
• 종이(배열) 안의 숫자들이 모두 같다면, 그 종이는 분할하지 않고 넘어간다.(숫자에 맞는 색종이 카운트)
• 종이 내에 다른 숫자가 하나라도 포함된다면, 그 종이를 4분할 한다.
• 4분할한 종이 하나하나마다 숫자가 같은지 확인한다.(1번부터 반복)

 

 

 

 

 

 

【 코드 】

 

#include<iostream>
using namespace std;

int paper[129][129];
int cnt_white;
int cnt_blue;

bool issame(int y,int x,int n) {
	int num = paper[y][x];

	for (int i = y; i < y + n; i++)
		for (int j = x; j < x + n; j++)
			if (num != paper[i][j])
				return false;

	return true;
}

void div(int y, int x, int n) {
	if (issame(y, x, n)) {
		if (paper[y][x] == 0)
			cnt_white++;
		if (paper[y][x] == 1)
			cnt_blue++;
	}
	else {
    		// 분할한 종이의 숫자들이 모두 같지 않다면 범위를 2로 나눈다.
		int vol = n / 2;

		// 이 부분이 핵심이다.
        	// 4분할을 했을 때 또 숫자가 모두 같지 않다면
            	// 그 종이에 대해 또 4분할해서 검사하는 코드이다.
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++)
				div(vol * i + y, vol * j + x, vol);
	}
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) 
			cin >> paper[i][j];

	div(0, 0, n);

	cout << cnt_white << '\n' << cnt_blue;

	return 0;
}