[재귀]-기본-종이의 개수

< 재귀 > - < 실버 2 >

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

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로만 채워진 종이의 개수를 출력한다.

---

 

로직은 알맞게 생각해냈는데 9등분하는 과정에서 9등분 한 걸 새로운 2차원배열에 담아서 보내려고 했었는데 그냥 종이를 저장하는 2차원 배열을 전역변수로 선언해두고 인덱스를 넘겨주면 되는 문제였당 ㅎ ,,

 

  답안  코드  

#include <iostream>
#include <algorithm>
// 지수승 사용
#include <math.h>

using namespace std;

int N;
int paper[2200][2200];
// -1, 0, 1로 채워진 종이 갯수
int cnt[3]; 

// 해당 종이 내부에 같은 숫자로만 채워졌는지 확인하는 함수
bool check(int x, int y, int n) {
	for (int i = x; i < x + n; i++)
		for (int j = y; j < y + n; j++) {
			if (paper[x][y] != paper[i][j]) return false;
		}
	return true;
}

void solve(int x, int y, int z) {
	if (check(x, y, z)) {
		// 종이 내부가 모두 같은 숫자라면
		// [해당숫자 +1] 을 증가시킴
		// -1 => 0
		// 0 => 1
		// 1 => 2
		cnt[paper[x][y] + 1] += 1;
		return;
	}
	// 9등분 해서 다시 solve() 호출
	int n = z / 3;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			solve(x + i * n, y + j * n, n);
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

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

	solve(0, 0, N);

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