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

📕문제

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

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

📕입력

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

📕출력

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

---

🔎문제 해석

이러한 문제가 전형적인 분할 정복의 문제인 것  같다.
조건에 부합하지 않으면 9등분으로 분할해서 다시 조건을 검사하고 조건에 맞으면 분할을 멈추고 하는 그러한 문제...
우선 종이를 검사해서 하나라도 다른 요소가 있다면 그 즉시 9 등분하고 각각의 등분에서 또 검사하고, 요소가 계속 다르더라도 종이의 개수가 한 개면 [임계점] 분할을 그만하고 그 요소에 따라 종이의 개수를 더해주면 된다.

 

⚡구현

우선 나는 재귀 함수로 계속 종이를 분할했다. [자세한 재귀 함수는 아래에 설명할 것이다]

 

💻종이의 구성요소를 검사하는 함수

종이의 첫 번째 원소를 기준으로 하나라도 다르다면 그 즉시 cp를 false로 초기화하고 만약 원소가 같다면 그대로 cp의 초기값인 true가 반환될 것이다.

--> checkpaper값이 true라면 종이의 모든 구성요소가 같다는 뜻.  --> sumpaper 실행

                               false라면 종이의 구성요소가 하나라도 다르다는 뜻--> 분할해야 함. [재귀 함수 실행]

 

💻종이의 개수를 더해주는 함수

우선 이 함수가 실행되는 조건이 모든 종이가 같은 숫자기 때문에 편의상 제일 첫 번째 원소를 기준으로 

-1,0,1에 따라 각각 sum 배열에 더해줬다.

💻재귀 함수 내부

재귀함수 내부에서 9등분을 어떻게 구현했냐면

각각의 첫 번째 시작점을 인자로 넘겨주고 배열의 크기를 넘겨주면서 배열을 구분했다.

예를 들어 makepaper(0,0, Size) 면 (0,0)에서 시작하는 배열이고 배열의 크기는 Size*Size라는 뜻이다.

그렇다면 makepaper(0+2*Size,2+Size, Size)는 어떤 배열을 넘겨줄까?

위의 배열을 넘겨줄 것이다. 이렇게 나는 각 행, 열 의 시작 인자와 배열의 크기를 넘겨주면서 큰 배열을 분할했다.

📃코드

/*
백준 실버2 종이의 개수
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<vector<int>> graph;
vector<int> sum(3);
void makepaper(int row, int col, int size);
bool checkpaper(int row, int col, int size);
void sumpaper(int row, int col);
int main()
{
    cin >> n;
    graph.resize(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> graph[i][j];
        }
    }
    makepaper(0,0,n);
    for (int i = 0; i < sum.size(); i++)
    {
        cout << sum[i] << endl;
    }
}
void makepaper(int row, int col, int size)
{
    int Size = size / 3;
    if (Size < 1) //최소 크기일때 병합해야할까?
    {
        //cout << "종이의 분할가능 크기는 최소 1입니다" << endl;
        return; //
    }
    else
    {
        if (checkpaper(row,col,size) == true)
        {
            sumpaper(0, 0);
            return;
        }
        if (checkpaper(row, col, Size) == false)
        {
            // cout << "graph1 is not same" << endl;
            makepaper(row, col, Size);
        }
        else
        { // true면 모두 같은 종이의 구성요소가 있다는 뜻이다.
           // cout << "graph1 is same." << endl;
            sumpaper(row, col);
        }
        if (checkpaper(row,col + Size, Size) == false)
        {
            // cout << "graph2에 종이의 요소는 모두 같지 않습니다" << endl;
            makepaper(row, col + Size, Size);
        }
        else
        {
            // cout << "graph2 is  same" << endl;
            sumpaper(row, col + Size);
        }
        if (checkpaper(row, col + 2 * Size, Size) == false)
        {
            // cout << "graph3 is not same" << endl;
            makepaper(row, col + 2 * Size, Size);
        }
        else
        {
            //cout << "graph3 is same" << endl;
            sumpaper(row, col+ 2 * Size);
        }
        if (checkpaper( row + Size, col, Size) == false)
        {
            //cout << "graph4 is not same" << endl;
            makepaper(row + Size, col, Size);
        }
        else
        {
            // cout << "graph4 is same" << endl;
            sumpaper(row + Size, col);
        }
        if (checkpaper( row + Size, col + Size, Size) == false)
        {
            // cout << "graph5 is not same" << endl;
            makepaper(row + Size, col + Size, Size);
        }
        else
        {
            // cout << "graph5 is same" << endl;
            sumpaper(row+ Size, col + Size);
        }
        if (checkpaper( row + Size, col + 2 * Size, Size) == false)
        {
            // cout << "graph6 is not same" << endl;
            makepaper( row + Size, col+ 2 * Size, Size);
        }
        else
        {
            //cout << "graph6 is same" << endl;
            sumpaper( row + Size, col + 2 * Size);
        }
        if (checkpaper( row + 2 * Size, col, Size) == false)
        {
            // cout << "graph7 is not same" << endl;
            makepaper( row + 2 * Size, col, Size);
        }
        else
        {
            // cout << "graph7 is same" << endl;
            sumpaper( row + 2 * Size, col);
        }
        if (checkpaper( row + 2 * Size, col + Size, Size) == false)
        {
            // cout << "graph8 is not same" << endl;
            makepaper(row + 2 * Size, col + Size, Size);
        }
        else
        {
            // cout << "graph8 is same" << endl;
            sumpaper(row + 2 * Size, col + Size);
        }
        if (checkpaper(row + 2 * Size, col + 2 * Size, Size) == false)
        {
            // cout << "graph9 is not same" << endl;
            makepaper( row + 2 * Size, col + 2 * Size, Size);
        }
        else
        {
            // cout << "graph9 is same" << endl;
            sumpaper( row+ 2 * Size, col+ 2 * Size);
        }
    }
}
void sumpaper(int row, int col)
{
    int num = graph[row][col];
    switch (num)
    {
    case -1:
        sum[0] += 1;
        break;
    case 0:
        sum[1] += 1;
        break;
    case 1:
        sum[2] += 1;
        break;
    }
}
bool checkpaper(int row, int col, int s)
{
    int check = graph[row][col]; //-1,0,1 아닌 숫자면 가능
    bool cp = true;
    for (int i = row; i < row+s; i++)
    {
        if (cp == false)
        {
            break;
        }
        for (int j = col; j <col+s; j++)
        {
            if (check != graph[i][j]) {
                cp = false;
                break;
            }
        }
    }
    return cp;
}

 

✔느낀 점

• 초기에는 배열 9개를 매번 만들어서 함수의 인자로 넘겨줬는데 시간 초과가 났다..ㅜㅜ
  • 이유는 함수 인자에 배열을 넘겨주면 매번 함수가 실행될 때마다 배열이 복사되는 시간이 발생해서 당연히 시간 초과가 나는 것이다.
• 이러한 분할 정복은 하나의 배열을 가지고 계속해서 쪼개는 문제인데 너무 날먹으로 풀려고 했던 것 같다 ㅎㅎ..
• 재귀 함수 내부를 더욱 깔끔하게 짤 수 있었을 거 같음(if문을 남발했는데 안 하고 전체를 반복문으로 해도 좋았을 듯?)
• 분할 정복의 개념이 헷갈렸는데 이번 종이의 개수 문제가 딱 전형적인 분할 정복을 맛보기 좋았던 문제인 것 같다.