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

문제

백준 2630

2630번: 색종이 만들기

풀이

정해진 크기 만큼의 배열을 돈 뒤, 색깔이 모두 같으면 해당 색깔 개수를 늘려주고

색깔이 다르면 재귀를 통해 분할정복합니다.

fun함수는 시작지점 sx, sy와 크기 size를 받습니다.

map[sy][sx]에 따라 색깔을 나눈 뒤, 배열을 size만큼 점검합니다.

해당 배열의 색깔이 모두 같으면 해당색깔++을 해줍니다.

다르면 4개 영역으로 분할합니다. 각각 좌상 / 우상 / 좌하 / 우하 입니다.

소스 코드

#include<iostream>
using namespace std;
 
bool color;
int bluesum;
int whitesum;
int n;
bool map[129][129];
 
void fun(int sx, int sy, int size)
{
    bool check = true;
    // 색깔 점검
    if (map[sy][sx] == 1)
        color = 1;
    else
        color = 0;
    // 범위에 다른 색깔 있는지 확인
    for (int i = sy; i < sy + size; i++)
    {
        for (int j = sx; j < sx + size; j++)
        {
            if (map[i][j] != color)
            {
                check = false;
                break;
            }
        }
        if (!check)
            break;
    }
    // 다른 색깔 없으면
    if (check)
    {
        if (color)
            bluesum++;
        else
            whitesum++;
    }
    // 다른 색깔 있으면
    else
    {
        int nsize = size / 2;
        fun(sx, sy, nsize);
        fun(sx, sy + nsize, nsize);
        fun(sx + nsize, sy, nsize);
        fun(sx + nsize, sy + nsize, nsize);
    }
}
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            cin >> map[i][j];
    }
    fun(1, 1, n);
    cout << whitesum << endl << bluesum;
    return 0;
}