백준1780 - 종이의 갯수

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

1780번: 종이의 개수

분할 정복 문제다. 각 종이의 모든 칸을 탐색한 다음 하나의 숫자만으로 이루어져 있는지 확인하고 그렇지 않다면 종이를 가로와 세로로 3등분 하여 다시 재탐색한다. 기본 문제이니 잘 알아두도록 해야겠다.

#include <iostream>
#include <cmath>
using namespace std;
const int len = 3 * 3 * 3 * 3 * 3 * 3 * 3;

int cnt[3] = { 0, }; //-1, 0, 1중 단 하나만 있는 종이를 세는 변수
int mat[len + 1][len + 1] = { 0, }; //최대 3^7 + 1칸을 가로, 세로로 잡는다.

//분할 정복을 이용한 종이 자르기
void func(int x, int y, int l) {
    int num = mat[x][y]; //제일 왼쪽 위에 칸에 적혀 있는 숫자를 저장
    bool check = true; //종이에 단 하나의 숫자만 있는지 확인하는 변수, 처음에는 단 하나의 변수만 있다고 가정

    //종이에 단 하나의 변수만 있는지 탐색하는 과정
    for(int i = x; i < x + l; i++) {
        for(int j = y; j < y + l; j++) {
            if(num != mat[i][j]) { //다른 숫자가 나오면
                check = false; //단 하나의 숫자만 있지 않다고 바꾸고
                break; //탈출
            }
        }
        if(!check) { //단 하나의 숫자만 있지 않다면
            break; //탈출
        }
    }
    
    if(check) { //종이에 숫자가 하나인 경우
        if(num == -1) { //-1만 있는 경우
            cnt[0]++;
        }
        else if(num == 0) { //0만 있는 경우
            cnt[1]++;
        }
        else { //1만 있는 경우
            cnt[2]++;
        }
    }
    else { //그 외의 경우는 3등분하여 재탐색(분할)
        func(x, y, l / 3);
        func(x, y + l / 3, l / 3);
        func(x, y + (l / 3) * 2, l / 3);
        func(x + l / 3, y, l / 3);
        func(x + l / 3, y + l / 3, l / 3);
        func(x + l / 3, y + (l / 3) * 2, l / 3);
        func(x + (l / 3) * 2 , y, l / 3);
        func(x + (l / 3) * 2, y + (l / 3), l / 3);
        func(x + (l / 3) * 2, y + (l / 3) * 2, l / 3);
    }
}

int main() {
    int n;
    cin >> n;
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> mat[i][j];
        }
    }
    
    func(1, 1, n); //탐색 시작, 처음 위치는 맨 왼쪽 맨 위에서 길이 n으로 탐색 시작
    
    for(int i = 0; i < 3; i++) {
        cout << cnt[i] << '\n';
    }
    
}