[백준/2630/C] 색종이 만들기

만약 색종이의 모든 부분이 같으면 그 색상의 카운트를 추가해주고 아니라면 분할정복으로 반복하도록 만드는 재귀알고리즘을 짜면된다.

#include <stdio.h>

int paper[128][128];
int white=0, blue=0;

void divide(int x, int y, int N){
    if (N==0) return;
    int par=0;
    for(int i=x; i<x+N; i++){
        for(int j=y; j<y+N; j++){
            if (paper[i][j]) par++;
        }
    }
    if (par==0) {
        white++; return;
    }
    if (par==N*N) {
        blue++; return;
    }
    
    divide(x,y,N/2);
    divide(x+N/2,y,N/2);
    divide(x,y+N/2,N/2);
    divide(x+N/2,y+N/2,N/2);
}

int main(){
    int N; scanf("%d",&N);
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            scanf("%d", &paper[i][j]);
        }
    }
    divide(0,0,N);
    printf("%d\n%d",white, blue);
}