[ 백준 2630 ] 색종이 만들기 (C++)

백준의 색종이 만들기(2630) 문제이다.

[ 문제 바로가기 ]

 

[ 문제풀이 ]

주어진 사각형을 N / 2로 나눠가면서 색깔을 파악할 때, 주어진 맵에서 파랑색과 하얀색 색종이는 총 몇개가 있는지 구해야 하는 문제이다. 다양한 예시를 통해서 정답을 도출하는 과정을 진행해보자.

 

#Case 1.

위와 같이 8 x 8 크기의 맵이 모두 하얀색 색종이로만 이루어진 경우를 보자.

위의 경우는 정답이 어떻게 될까 ???

하얀색 색종이 = 1개 , 파랑색 색종이 = 0개가 정답이 될 것이다.

이를 어떻게 파악할 수 있을까 ??

8 x 8 크기의 맵을 모두 탐색을 해보면서, 하얀색으로만 이루어져있는지 혹은 파랑색으로만 이루어져있는지를 파악하면 된다. 위의 경우는 하얀색으로만 이루어져있다는 판단이 있었으므로 하얀색 색종이 1개면 위의 맵을 모두 채울 수 있다라고 생각을 할 수 있다.

 

#Case2.

그럼 위의 경우를 보자. 위의 경우는 어떻게 될까 ??

파랑색 색종이는 1개, 하얀색 색종이 3개로 이루어져 있다는 것을 알 수 있다.그럼 이를 어떻게 판단해줄 수 있을지 이야기를 해보자. #Case1과 같이 8 x 8 크기의 맵을 모두 탐색해 보았더니, 하얀색으로만 이루어져있지도 않았고, 파랑색으로만 이루어져 있지도 않았다. 따라서, 8 x 8에서는 판단이 불가하기 때문에 더 작은 사각형인 4 x 4 크기의 사각형 4개로 나눠주면 된다.

즉 ! 위와 같이 사각형을 4개로 나눠본 것이다. 나눠진 4개의 사각형은 각각, 하얀색으로만 그리고 파랑색으로만 이루어져 있다는 것을 알 수 있다. 2개의 색 중 어느 하나의 색으로만 가득 채워져 있다면 더 이상의 탐색이 필요하지 않다는 것이다.

만약 그렇지 않다면, 계속해서 "현재 길이 / 2" 로 사각형을 쪼개가면서 탐색을 진행하면 된다.

탐색을 더 이상 하지 않아도 되는 기저조건은 "현재길이가 '1'인 경우" 가 될 것이다. 1을 더이상 쪼갤 수는 없을 뿐더러, 길이가 1인 사각형은 "반드시 하얀색 or 파랑색 둘 중 하나의 색깔로만 채워져 있을 것이기 때문" 이다.

 

#3. 구현

그렇다면 이 과정들을 어떻게 구현할 수 있을까 ?? 본인은 이를 "재귀"를 통해서 구현해 주었다.

재귀로 구현한다면 가장 중요한 것은 "재귀함수에 사용되는 '인자'" 가 될 것이다.

본인은 [ 시작 x좌표 , 시작 y좌표 , 현재 사각형의 한 변의 길이 ] 이 3개의 정보를 인자로 사용해 주었다.

위에서 진행했던 길이가 '8'인 사각형으로 예를 들어보면, 가장 초기에 호출되는 재귀함수의 값은 (0 , 0 , 8) 이 될 것이다.

만약, 위와 같이 호출을 했을 때, 하나의 색깔로만 이루어져있지 않아서 이후의 탐색을 해야 한다면 어떻게 호출을 해줘야할까 ??

길이가 N / 2로 나누는 순간, 사각형은 총 4개가 더 생기게 된다. 실제로 #Case1 에서 #Case2로 갈 때 4개의 사각형이 생기게 되었다. 그럼 이 4개의 사각형의 시작좌표와 길이를 호출을 해주면 되는 것이다.

즉 ! 총 4개의 재귀함수를 더 호출하게 될 것이다.

그럼 현재 시작좌표가 (x , y)이고 길이가 N일 때, 이 다음의 탐색을 위해서는 다음과 같이 4가지 영역에 대한 탐색을 진행해 주어야 한다.

(x , y , N / 2)

(x , y + N / 2 , N / 2)

(x + N / 2 , y , N / 2)

(x + N / 2 , y + N / 2 , N / 2)

위와 같이 재귀를 반복하면서 색을 판단할 수 있다.

 

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 130
using namespace std;
 
int N, Blue, White;
int MAP[MAX][MAX];
 
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)
{
    bool Zero, One;
    Zero = One = true;
    for (int i = x; i < x + Size; i++)
    {
        for(int j = y; j <y + Size; j++)
        {
            if (MAP[i][j] == 1) Zero = false;
            if (MAP[i][j] == 0) One = false;
        }
    }
 
    if (Zero == true) { White++; return; }
    if (One == true) { Blue++; return; }
    
    DFS(x, y, Size / 2);
    DFS(x, y + Size / 2, Size / 2);
    DFS(x + Size / 2, y, Size / 2);
    DFS(x + Size / 2, y + Size / 2, Size / 2);
}
 
void Solution()
{
    DFS(0, 0, N);
    cout << White << endl << Blue << 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;
}