[알고리즘]BOJ_1780(종이의 개수)

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

문제

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다.

만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
(1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.
이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

정답코드

#include<bits/stdc++.h>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n'

using namespace std;

int zero_cnt = 0;
int plus_cnt = 0;
int minus_cnt = 0;

int finder(int y, int x, int end_y, int end_x, vector<vector<int>>& v)
{
    int post=v[y][x];

    for(int i=y; i<end_y; i++)
    {
        for(int j=x; j<end_x; j++)
        {
            if(post!=v[i][j]) return -2;
            post=v[i][j];
        }
    }

    return post;
}

void rec(int y, int x,vector<vector<int>>& v, int n)
{
    int size = n;

    int num = finder(y,x,y+size,x+size,v);
    
    if(num == 1)    plus_cnt++;
    else if(num == 0)   zero_cnt++;
    else if(num == -1)  minus_cnt++;
    else
    {
        for(int i=y; i<y+size; i+=size/3)
        {
            for(int j=x; j<x+size; j+=size/3)
            {
                rec(i,j,v,size/3);
            }
        }
    }

    return ;
}

int main()
{
    FASTio;

    int n;

    cin >> n;

    vector<vector<int>> v(n,vector<int> (n,0));

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin >> v[i][j];


    rec(0,0,v,n);

    cout << minus_cnt << endl;
    cout << zero_cnt << endl;
    cout << plus_cnt << endl;

    return 0;
}

풀이 및 사고과정

문제를 보고 문제의 유형과 어떻게 풀어야할지 바로 감이 잡혔다.
근데 재귀적으로 사고하는 과정에서 범위를 어떻게 넣어야할지 헤매다 결국 많은 시간을 소비하고 말았다.

이 문제는 모든 수가 일정하지 않으면 그 자리에서부터 범위를 좁혀 해당 행위를 반복하면 되는 문제이다. 그렇게 finder함수에 -1,0,1이 아니면 그 자리에서부터 나누기 3만큼 범위를 좁혀 다시 finder함수에 넣어 확인하면 되는 것이다.

옛날에도 그랬듯이 재귀적으로 사고하는 능력이 다소 부족한 것 같다.
이런 유형의 문제를 많이 풀어서 익혀야 할 것 같다.