[BOJ] 2630번 | 색종이 만들기 (C++)

🔗문제 보러가기

2630번: 색종이 만들기

 

🧑🏻‍💻풀이 과정

맨 처음에는 \( N \times N \) 크기의 색종이부터 시작하여 주어진 정사각형 내의 색깔들이 모두 같은 색깔인지를 볼 겁니다. 이 때, 선택지는 두 가지로 나뉘게 됩니다.

1. 주어진 범위 내의 색깔이 모두 같은가?  \( \rightarrow \)  해당 색깔 개수 +1하고, 종료
2. 색깔이 같지 않은가?  \( \rightarrow \)  주어진 범위의 사각형을 4등분하여 다시 탐색 시작

 

정사각형 탐색은 맨 왼쪽 위부터 열 방향으로 시작할 것이며, 이 시작 지점의 행, 열을 (rowBegin, colBegin)이라고 합시다.

해당 정사각형 내의 색깔이 모두 같은 1번 케이스의 경우에는 해당 색깔 개수를 +1 해주고 끝내면 됩니다.

 

 

하지만, 2번 케이스에 해당하는 경우에는 N을 반으로 나눈 후에 다시 탐색을 시작해야 합니다.

N을 반으로 나눈 다음 탐색에서의 I, II, III, IV의 rowBegin, colBegin 값들은 다음과 같습니다.

(rowBegin, colBegin)                      // I
(rowBegin, colBegin + (N / 2))            // II
(rowBegin + (N / 2), colBegin)            // III
(rowBegin + (N / 2), colBegin + (N / 2))  // IV

 

위의 행, 열을 시작점으로 하여 각각의 영역에서 탐색을 시작하면 됩니다.

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
using namespace std;
using Square = vector<vector<int>>;
using Line = vector<int>;

void Search(const Square& coloredPaper, vector<int>& counts, int N, int rowBegin, int colBegin)
{
    if (N == 1)
    {
        int color = coloredPaper[rowBegin][colBegin];
        counts[color]++;
        return;
    }

    int color = -1;
    bool isAllEqaul = true;
    for(int row = rowBegin; row < rowBegin + N; row++)
    {
        for (int col = colBegin; col < colBegin + N; col++)
        {
            // 첫 부분 색깔 얻기
            if (row == rowBegin && col == colBegin)
            {
                color = coloredPaper[row][col];
                continue;
            }

            // 영역 내에 색깔이 다른 게 있을 경우, 반복문 종료
            if (color != coloredPaper[row][col])
            {
                isAllEqaul = false;
                break;
            }
        }

        if (!isAllEqaul)
            break;
    }


    // 영역 내의 색깔이 모두 같을 경우, 해당 색깔 개수 +1
    if (color != -1 && isAllEqaul)
    {
        counts[color]++;
        return;
    }

    int next = N / 2;
    Search(coloredPaper, counts, next, rowBegin, colBegin);                 // I
    Search(coloredPaper, counts, next, rowBegin, colBegin + next);          // II
    Search(coloredPaper, counts, next, rowBegin + next, colBegin);          // III
    Search(coloredPaper, counts, next, rowBegin + next, colBegin + next);   // IV
}


int main()
{
    FAST_IO;

    int N;
    cin >> N;

    Square coloredPaper(N, Line(N));
    for (int i = 0; i < N; i++)
        for (int k = 0; k < N; k++)
            cin >> coloredPaper[i][k];

    vector<int> counts { 0, 0 };
    Search(coloredPaper, counts, N, 0, 0);

    for (const auto& color : counts)
        cout << color << "\n";
    return 0;
}