[백준/C,C++] 2630번: 색종이 만들기

www.acmicpc.net/problem/2630

2630번: 색종이 만들기

대표적인 분할 정복 문제입니다. 재귀로 간단하게 구현할 수 있습니다. 파라미터로 받아온 배열 범위 안 원소값이 모두 0이라면 흰색, 모두 1이라면 파란색의 개수를 증가 시켜 줍니다. 그 외 색이 섞인 색종이라면 다시 한번 4등분하여 함수를 재귀 호출합니다.

#include<iostream>

using namespace std;

int paper[128][128];
int n, white, blue;

void quad(int x, int y, int len)
{
    if (len == 0) return;
    int color = 0;
    for (int i = y; i < y + len; i++) {
        for (int j = x; j < x + len; j++) {
            if (paper[i][j] == 1) color++;
        }
    }
    if (color == len * len) {
        blue++;
        return;
    }
    else if (color == 0) {
        white++;
        return;
    }
    else {
        int half = len / 2;
        quad(x, y, half);
        quad(x + half, y, half);
        quad(x, y + half, half);
        quad(x + half, y + half, half);
    }
    return;
}

int main(void)
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> paper[i][j];
        }
    }

    quad(0, 0, n);
    cout << white << "\n" << blue;

    return 0;
}