백준 1780번: 종이의 개수

[문제 링크]

1780번: 종이의 개수

---

https://onlytrying.tistory.com/46

쿼드트리 문제와 동일하다. 다른점은 보드 크기가 3^N X 3^N 인 것과 보드를 쪼갤 때 4조각이 아닌 9조각으로 쪼갠다는 것이다.

쿼드트리 문제와 마찬가지로 (startY, startX)좌표를 시작으로 3^N X 3^N 크기 만큼의 보드를 검사한다.

숫자가 모두 같다면 더이상 쪼개질 수 없으므로 보드의 숫자를 카운팅 해준다.

필자는 0으로 초기화한 크기가 3인 배열을 하나 만들고 Array[보드의 숫자 + 1]++ 으로 숫자를 카운팅하였다.

---

#include <iostream>
using namespace std;

int board[2188][2188];
int numberCnt[3]; // MINUS ONE = 0, ZERO = 1, ONE = 2

void Solution(int N, int startY, int startX)
{
	if (N == 1) // 없어도 무방한 기저사례지만 코드 직관성과 효율성을 위해 추가
	{
		++numberCnt[board[startY][startX] + 1];
		return;
	}

	bool check = true;
	for (int i = startY; i < startY + N; i++)
	{
		for (int j = startX; j < startX + N; j++)
		{
			if (board[startY][startX] != board[i][j])
			{
				check = false;
				break;
			}
		}
		if (!check) break;
	}
	if (check)
	{
		++numberCnt[board[startY][startX] + 1];
		return;
	}

	int nextN = N / 3;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			Solution(nextN, startY + (nextN*i), startX + (nextN*j));
}
int main(void)
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> board[i][j];

	Solution(N, 0, 0);

	for (int i = 0; i < 3; i++)
		cout << numberCnt[i] << endl;
	
	return 0;
}

알고리즘 200일 프로젝트 - 38day