[백준] 1780번 종이의 개수

문제 링크: https://www.acmicpc.net/problem/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로만 채워진 종이의 개수를 출력한다.

문제 이해

분할 정복문제이다.
색종이 만들기(https://velog.io/@kpg0518/%EB%B0%B1%EC%A4%80-2630%EB%B2%88-%EC%83%89%EC%A2%85%EC%9D%B4-%EB%A7%8C%EB%93%A4%EA%B8%B0) 문제와 매우 유사한 문제이다.
색종이 만들기에서는 4부분으로 분할했다면, 이 문제는 9부분으로 분할하는 문제이다.
들어온 부분이 다른 종이로 채워져있다면, 9부분으로 나눠주면 된다.

코드 구현(c++)

#include <iostream>

using namespace std;

int map[2187][2187];
int oneCnt = 0;
int zeroCnt = 0;
int minusOneCnt = 0;

bool check(int x, int y, int n){
    int temp = map[y][x];
    for(int i = y ; i < y+n ; i++){
        for(int j = x ; j < x+n ; j++){
            if(map[i][j] != temp) return false;
        }
    }
    return true;
}
void divide(int x, int y, int n){
    if(!check(x, y, n)){
        divide(x, y, n/3); //first floor1
        divide(x + n/3, y, n/3); // first floor2
        divide(x + n/3*2, y, n/3); // first floor3
        divide(x, y + n/3, n/3);  //second floor1
        divide(x + n/3, y + n/3, n/3); //second floor2
        divide(x + n/3*2, y + n/3, n/3); //second floor2
        divide(x, y + n/3*2, n/3);  //third floor1
        divide(x + n/3, y + n/3*2, n/3);  //third floor2
        divide(x + n/3*2, y + n/3*2, n/3); //third floor3
    }
    else {
        if(map[y][x] == 0) zeroCnt++;
        else if(map[y][x] == 1) oneCnt++;
        else minusOneCnt++;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    int num;
    cin >> num;
    for(int i = 0 ; i < num ; i++){
        for(int j = 0 ; j < num ; j++){
            cin >> map[i][j];
        }
    }
    divide(0, 0, num);
    cout << minusOneCnt << "\n" << zeroCnt << "\n" << oneCnt << "\n";
}