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

 

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

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

1780번: 종이의 개수

 

 

【 풀이 】

 

분할 정복 알고리즘과 재귀를 이용하여 해결하는 문제이다.

분할 정복 알고리즘이란 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 방법이다.

이 문제에 따르면

1. 종이(배열) 안의 숫자들이 모두 같다면, 그 종이는 분할하지 않고 넘어간다.
2. 종이 내에 다른 숫자가 하나라도 포함된다면, 그 종이를 9분할 한다.
3. 9분할한 종이 하나하나마다 숫자가 같은지 확인한다.(다시 1번으로 반복)

9*9 크기의 종이를 예로 들면,

9*9 크기에 채워진 숫자들, 즉 81칸의 숫자가 모두 같다면 -> n으로만 적혀있는 종이의 개수 ++

하나라도 다르다면 3*3 크기의 종이 9개로 분할

3*3 크기의 종이 하나하나 다시 체크 -> 모두 같다면 -> n으로만 적혀있는 종이의 개수 ++ -> 다음 종이로 넘어감

하나라도 다르다면 1*1 크기의 종이 9개로 분할

1*1이 된다면 칸이 하나밖에 없기 때문에 모두 같을 수밖에 없어 더 이상 분할하지 않는다.

즉 1*1 크기로 분할할 때까지 과정을 반복하는 것.

 

 

 

 

 

【 코드 】

 

#include<iostream>
using namespace std;

int cnt_1 = 0, cnt0 = 0, cnt1 = 0;
//	각각 -1이 적힌 종이, 0이 적힌 종이, 1이 적힌 종이의 개수를 나타내는 변수
int arr[2200][2200];

bool issame(int y, int x, int n) {		//	종이 내의 숫자들을 체크하는 함수
	int num = arr[y][x];
	for (int i = y; i < y + n; i++) {
		for (int j = x; j < x + n; j++) {
			if (num != arr[i][j]) {
				return false;
			}
		}
	}
	return true;
}

void div(int y, int x, int n) {
	if (issame(y, x, n)) {		//	종이 내의 숫자가 모두 같다면(true)
		if (arr[y][x] == -1) {
			cnt_1++;
		}
		else if (arr[y][x] == 0) {
			cnt0++;
		}
		else if (arr[y][x] == 1) {
			cnt1++;
		}
	}
	else {		//	종이 내의 숫자가 하나라도 다르다면(false)
		int volume = n / 3;		//	한 변의 길이를 1/3
		for (int i = 0; i < 3; i++) {		//	분할하면 한 변마다 3번씩만 반복
			for (int j = 0; j < 3; j++) {
				div(volume * i + y, volume * j + x, volume);
             		  	 //	1/3을 한 한 변의 길이와 분할했을 때의 위치 경우의 수들을 전달해서
                      		   //	또 숫자가 다르다면 계속 분할하는 형식임
			}
		}
	}
}

int main(void) {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
	div(0, 0, n);		//	처음 파라미터
	cout << cnt_1 << '\n' << cnt0 << '\n' << cnt1;
	return 0;
}