뚝딱뚝딱

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

💡 분할과 정복 ** 쿼드트리 문제와 유사

[문제]
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.(1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

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

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

✅ 문제 풀이

• 분할과 정복을 통해 해결할 수 있는 문제이다.
• 문제는 처음 size에서 3등분 해가며 분할한다.
• 입력으로 주어진 size에서 시작하여, size 만큼 배열을 순회한다.
• 순회하다가 첫 값과 달라지는 부분이 발생하면, 9등분으로 나뉘어야 하기 때문에, size를 3등분 한다.
• 그리고 해당 함수를 각 9등분의 첫 값의 좌표에 맞추어 9번의 재귀호출을 한다.
• 첫번째 조각의 첫 좌표는 이전의 첫 좌표와 항상 동일하고, 두번째 조각의 첫 좌표는 y를 size만큼 더한 값이고, 세번째 조각의 첫좌표는 y를 size*2만큼 더한 값이다.
• 네번째 조각의 첫좌표는 x를 size 만큼 더한 값이고, 다섯번째 조각의 첫좌표는 x와 y 모두 size 만큼 더한 값이다...
• 이렇게 9등분을 차례차례 좌표를 부여하고 재귀호출 하면된다.
• 재귀호출 뒤에는 동작이 없기 때문에 바로 return하도록 하고, 만약 해당 size에서 모든 값이 동일했다면, 해당 값을 1 count하도록 한다.
• 이때 카운트는 map을 통해서 -1, 0,1을 key로 하였고, 0으로 자동 초기화 되는 값에 증가 연산자로써 연산되도록 구현하였다.  

✏ 코드 전문

#include<iostream>
#include<vector>
#include<map>

using namespace std;

int n;
vector<vector<int>> arr;
map<int, int> m;

void func(int size, int x, int y) {
	for (int i = x; i < x + size; i++) {
		for (int j = y; j < y + size; j++) {
			if (arr[x][y] != arr[i][j]) {
				int new_size = size / 3;
				func(new_size, x, y);
				func(new_size, x, y + new_size);
				func(new_size, x, y + new_size * 2);
				func(new_size, x + new_size, y);
				func(new_size, x + new_size, y + new_size);
				func(new_size, x + new_size, y + new_size * 2);
				func(new_size, x + new_size * 2, y);
				func(new_size, x + new_size * 2, y + new_size);
				func(new_size, x + new_size * 2, y + new_size * 2);
				return;
			}
		}
	}
	m[arr[x][y]]++; //해당 키가 map에 없으면, 자동으로 키 생성 및 0으로 초기화하고 증가시킴.
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	arr.resize(n, vector<int>(n));

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

	func(n, 0, 0);

	cout << m[-1] << "\n" << m[0] << "\n" << m[1];

	return 0;
}