BOJ 1780, 종이의 개수

대표적인 분할 정복 문제입니다.

3^n by 3^n으로 이루어진 타일 중, 3^a by 3^a (a= 1,2,3,4. ..)로 이루어진 타일이 몇 개가 있는지 세어보는 문제입니다.

분할정복 문제는 대부분 재귀호출로 해결해야 합니다.

이에 대한 구체적인 알고리즘은 예제로 알려드리도록 하겠습니다.

처음엔, 파란색 네모의 모든 칸을 조사해서 같은 색깔인지 판단합니다.

당연히 아니니, 멈추지 않고 다음 단계로 넘어갑니다.

다음 단계는 파란색 네모를 9개의 칸으로 나눈 다음, 각 칸에 대한 문제를 해결합니다.

각 빨간색 네모에 대해, 문제를 해결해 봤더니 6개의 종이를 얻었습니다. (3 by 3 size 종이 6개)

-1로 채워진 종이는 1개,

 1로 채워진 종이는 2개

0으로 채워진 종이는 3개 입니다. 

찾은 종이는 모두 

이제 나머지 종이로 가봐야 합니다. (아래의 3개를 1by 1크기의 종이로 쪼갬)

 

종이를 쪼개봤더니, 1by 1 size의 종이 중,

-1로 채워진 종이는 9개

 1로 채워진 종이는 9개

0으로 채워진 종이는 9개가 있습니다.

따라서 총 합은, 

-1로 채워진 종이 10개

 1로 채워진 종이 11개

 0으로 채워진 종이 12개가 되어

답이

10

11

12

가 출력되는 것입니다.

소스코드는 아래와 같습니다.

소스코드를 잘 분석하셔서, 분할 정복 풀이에 익숙해지도록 합시다 :)

#include <iostream>
#include <cstdio>
 
using namespace std;
 
int n;
int board[2500][2500];
int ans[3];
 
void solve(int, int, int);
 
 
int main()
{
    scanf("%d", &n);
    for (int i = 0; i<n; ++i) {
        for (int j = 0; j<n; ++j) {
            scanf("%d", &board[i][j]);
        }
    }
 
    solve(0, 0, n);
    for (int i = 0; i<3; ++i) printf("%d\n",ans[i]);
}
 
void solve(int x, int y, int cur)
{
    int first = board[x][y];
    bool isallsame = true;
    for (int i = x; i<x + cur; ++i) {
        for (int j = y; j<y + cur; ++j) {
            if (first != board[i][j]) {
                isallsame = false;
                break;
            }
        }
        if (!isallsame)break;
    }
    if (isallsame) {
        ans[first + 1]++;
        return;
    }
    int k = cur / 3;
    for (int i = 0; i<3; ++i) {
        for (int j = 0; j<3; ++j) {
            solve(x + i*k, y + j*k, k);
        }
    }
}