[ 백준 1780 ] 종이의 개수 (C++)

백준의 종이의 개수(1780) 문제이다.
[ 문제 바로가기 ]

[ 문제풀이 ]

주어진 현재 크기에서 9개의 영역으로 나누어서 탐색을 진행하면 되는 문제이다.

입력으로 주어지게 되는 맵을 보게 되면 9 x 9 짜리 맵인데, 이 맵을 3 x 3 짜리 9개의 맵으로 나누는 것이다.

나눴을 때, 해당 맵이 -1, 0, 1 3개의 값 중 하나의 값으로만 채워져 있다면 해당 숫자의 갯수를 ++ 시켜주면 된다.

그게 아니라면, 3 x 3 짜리 맵을 1 x 1 짜리 9개의 칸으로 또 나눠서 체크를 하면 된다.

1 x 1 짜리는 값이 하나밖에 존재할 수 없기 때문에 무조건 -1, 0, 1 3개의 값 중 하나의 값으로만 채워져 있게 된다.

[ 소스코드 ]

#include<iostream>
#include<cmath>
 
#define endl "\n"
#define MAX 2197
using namespace std;
 
int N;
int MAP[MAX][MAX];
int Answer[3];
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void DFS(int x, int y, int Size)
{
    if (Size == 1)
    {
        Answer[MAP[x][y] + 1]++;
        return;
    }
 
    bool Zero, Minus, Plus;
    Zero = Minus = Plus = true;
    for (int i = x; i < x + Size; i++)
    {
        for (int j = y; j < y + Size; j++)
        {
            if (MAP[i][j] == -1) Zero = Plus = false;
            if (MAP[i][j] == 0) Minus = Plus = false;
            if (MAP[i][j] == 1) Zero = Minus = false;
        }
    }
    if (Minus == true)
    {
        Answer[0]++;
        return;
    }
    if (Zero == true)
    {
        Answer[1]++;
        return;
    }
    if (Plus == true)
    {
        Answer[2]++;
        return;
    }
 
    int NextSize = Size / 3;
    DFS(x, y, NextSize);
    DFS(x, y + NextSize, NextSize);
    DFS(x, y + NextSize * 2, NextSize);
    
    DFS(x + NextSize, y, NextSize);
    DFS(x + NextSize, y + NextSize, NextSize);
    DFS(x + NextSize, y + NextSize * 2, NextSize);
 
    DFS(x + NextSize * 2, y, NextSize);
    DFS(x + NextSize * 2, y + NextSize, NextSize);
    DFS(x + NextSize * 2, y + NextSize * 2, NextSize);
}
 
void Solution()
{
    DFS(0, 0, N);
    for (int i = 0; i < 3; i++) cout << Answer[i] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}