백준 1780번 : 종이의 개수

문제 링크 : https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

 문제 설명  

 

N x N 크기의 행렬로 표현되는 종이가있고 종이는 1,0,-1로 채워져있다 

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 9등분하고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.
3. 마지막에  -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수 출력

 

 알고리즘 

 

1. 재귀 함수를 이용하여 처음에 주어진 NxN크기의 행렬을 검사

2. 만약 9등분해야된다면 9등분해서 9개의 종이를 각각 또 검사 ....

3. N=1 까지 갔을때는 종이에 적힌 수 를 cnt++ 

 

 코드 

#include<iostream>
using namespace std;
 
int N;
int arr[2500][2500];
int ans[3];
 
void func(int n, int y, int x) {
 
    if (n == 1) {
        ans[arr[y][x] + 1]++;
        return;
    }
 
    bool a = true, b = true, c = true;
    for (int i = y; i < y + n; i++) {
        for (int j = x; j < x + n; j++) {
 
            //arr[i][j]가 -1 이면 0과 1로 이칸은 다채워질 수없음 
            if (arr[i][j] == -1) {
                b = false;
                c = false;
            }
 
            //arr[i][j]가 0 이면 -1과 1로 이칸은 다채워질 수없음 
            else if (arr[i][j] == 0) {
                a = false;
                c = false;
            }
 
            //arr[i][j]가 1 이면 -1과 0으로 이칸은 다채워질 수없음 
            else if (arr[i][j] == 1) {
                b = false;
                a = false;
            }
        }
    }
    if (a) ans[0]++;
    else if (b) ans[1]++;
    else if (c) ans[2]++;
    //만약 현재 칸이 한가지 숫자로 다 채워져 있지 않다면 9등분해서 재귀
    else {
 
        for (int i = y; i < y + n; i = i + n / 3) {
            for (int j = x; j < x + n; j = j + n / 3) {
                func(n / 3, i, j);
            }
        }
    }
    return;
}
 
int main() {
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
        }
    }
 
    //-1
    ans[0] = 0;
    //0
    ans[1] = 0;
    //1
    ans[2] = 0;
    func(N, 0, 0);
    cout << ans[0] << "\n" << ans[1] << "\n" << ans[2];
}