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

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

1780번: 종이의 개수

문제

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

---

풀이

전체를 여러 개로 분할하고 , 같은 알고리즘을 적용시켜 푸는 분할정복 문제이다.

종이 내의 숫자가 다 같으면 분할하지 않고 해당하는 값의 count를 +1해주고, 하나라도 다르면 9등분으로 분할한다.

좌표를 9등분해서 행,열 특성상 x,y를 바꿔서 함수를 호출하면 된다.

n이 3일 경우 9등분 했을때

---

#include <bits/stdc++.h>
using namespace std;
int arr[2188][2188];
int ans[3]; // [0] = -1, [1] = 0 , [2] = 1

void divide_conquer(int num, int x, int y) {

	int tmp = arr[y][x];
	bool same = true;
	if (num == 1) { // 쪼개서 하나만 남은 상황
		same = true;
	}
	else { 
		for (int i = y; i < num + y; i++) {
			for (int j = x; j < num + x; j++) {
				if (arr[i][j] != tmp) { // 다른 숫자가 있는 경우
					same = false;
					break;
				}
			}
		}
	}
	if (same) { // 만약 모두 숫자가 같더라면
		ans[tmp+1]++;
	}
	else {
		divide_conquer(num / 3, x,y); // 1번
		divide_conquer(num / 3, x+num/3, y); // 2번
		divide_conquer(num / 3, x + 2* (num / 3), y); // 3번

		divide_conquer(num / 3, x, y + num / 3); // 4번
		divide_conquer(num / 3, x + num / 3, y + num / 3); // 5번
		divide_conquer(num / 3, x + 2 * (num / 3), y + num / 3); // 6번

		divide_conquer(num / 3, x, y +2*( num / 3)); // 7번
		divide_conquer(num / 3, x + num / 3, y + 2*(num / 3)); // 8번
		divide_conquer(num / 3, x + 2 * (num / 3), y + 2 * (num / 3)); //9번
	}

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int num; cin >> num;
	int tmp;
	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++) {
			cin >> tmp;
			arr[i][j] = tmp;
		}
	}
	divide_conquer(num, 0, 0);

	for (int i = 0; i < 3; i++) {
		cout << ans[i] << "\n";
	}

	return 0;
} //main