[재귀 / BOJ 1780 / C++] 종이의 개수

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

1780번: 종이의 개수

 

재귀의 기본형인 문제. 앞으로 갖고올 문제들도 다 이거의 응용 아니면 동일한 문제다.

 

큰 개념은 

 

1) 하나의 숫자로(0, -1, 1) 채워져있는지 확인하고,
1-1) 만약 채워졌다면, 그 숫자를 확인한 후 개수를 세준다.
1-2) 만약 안채워졌다면, 사각형을 9등분한 후 각 사각형마다 다시 1) 과정을 반복한다. 

 

 

이런 논리로 재귀를 통해 해결할 수 있다. 말은 쉬우나 .. 구현이 처음할 때는 생각보다 어려웠다. 

 

#include <bits/stdc++.h>

using namespace std;

int N;
int paper[2200][2200];
int cnt[3];

bool chkfunc(int n, int r, int c){
    int chk = paper[r][c];

    for(int i = r; i < r+n; i++){
        for(int j = c; j < c+n; j++){
            if(chk!=paper[i][j]) return false;
        }
    }

    return true;
} // 숫자가 다른 것이 있는지 확인하는 함수.


void func(int n, int r, int c){
    if(chkfunc(n, r, c)) {
        cnt[paper[r][c]+1]++;
        return;
    } // 만약 같은 숫자로만 이뤄졌다면, 그 숫자의 개수를 늘려준다.


int k = n/3;
 for(int i = 0 ; i < 3 ; i ++){
    for(int j = 0 ; j < 3 ; j++){
        func(k, r+i*k, c+j*k);
    }
 } // 사각형 9등분하여 각각의 사각형에 과정 반복.

} 

int main(void){
    ios::sync_with_stdio(0);
    cin >> N;
    for(int i = 0 ; i < N ; i++ ){
        for(int j = 0 ; j < N ; j++){
            cin >> paper[i][j];
        }
    }

    func(N, 0, 0);

    for(auto i : cnt){
        cout << i << "\n";
    }

}