백준 1780 종이의 개수 / C++

문제 : 1780

풀이 point

재귀, 분할을 활용한 문제
보통의 분할 문제는 4분할이지만 이 문제는 9분할을 해야함
총 9분면을 봐야한다.

풀이 방법

재귀 함수
사각형 내의 요소가 모두 -1 or 0 or 1인지 확인하는 함수
-> 자세한 내용은 백준 2630 색종이 만들기 참고

코드

//백준 1780, 종이의 개수

#include <iostream>
#include <vector>
#include <queue>

int N;
int grid[3000][3000];
int zero{0}; int one{0}; int minus{0};

bool check(int n, int x, int y){
    int init = grid[x][y];
    for(int i{x}; i<x+n; ++i){
        for(int j{y}; j<y+n; ++j){
            if(grid[i][j] != init) return false;
        }
    }
    return true;
}

void recur(int n, int x, int y){
    if(check(n, x, y)){
        if(grid[x][y] == -1) ++minus;
        else if(grid[x][y] == 0) ++zero;
        else ++one;
    }
    else{
        int half3 = n/3;
        recur(half3, x, y);
        recur(half3, x, y+half3);
        recur(half3, x, y+2*half3);

        recur(half3, x+half3, y);
        recur(half3, x+half3, y+half3);
        recur(half3, x+half3, y+2*half3);

        recur(half3, x+2*half3, y);
        recur(half3, x+2*half3, y+half3);
        recur(half3, x+2*half3, y+2*half3);
        
    }
}

int main(){
    
    std::cin >> N;

    for(int i{0}; i<N; ++i){
        for(int j{0}; j<N; ++j){
            std::cin >> grid[i][j];
        }
    }
    
    recur(N, 0, 0);

    std::cout << minus << '\n' << zero << '\n' << one;
    return 0;
}

2025-01-12T02:58:59.754Z