[BOJ] 1992 쿼드 트리

문제: https://www.acmicpc.net/problem/1992

매우 쉬운 분할 정복 문제이다. 그냥 전구간이 하얀색/검은색인지 체크해서 분할하고 재귀함수로 넘겨주면 된다.

사실 재귀함수에 인자를 4개 줄 필요도 없고 (핵심) 모두가 검은색/하얀색인지의 판정도 $O(n^2)$으로 미리 전처리 해두면 $O(1)$로 찾을 수 있다. 그렇지만 귀찮기도 하고 굳이 그렇게 할 이유가 없기에 생략. 가장 좋은 알고리즘은 문제를 가까스로 풀 수 있는 알고리즘이다.

코드는 다음과 같다. 좀 더럽긴 하다. 난이도는 1.25/5

#include <cstdio>
#include <cmath>
 
char arr[70][70];
 
int check(int ax, int ay, int bx, int by)
{
    int sum=0;
    for(int i=ay;i<=by;i++)
        for(int j=ax;j<=bx;j++)
            sum+=arr[i][j]-'0';
    if(sum==0) return 0;
    if(sum==(bx-ax+1)*(bx-ax+1)) return 1;
    return -1;
}
 
void recur(int ax, int ay, int bx, int by)
{
    if(ax>bx || ay>by) return;
    int t=check(ax,ay,bx,by);
    if(t!=-1)
    {
        printf("%d",t);
        return;
    }
 
    printf("(");
 
    int midx=(ax+bx)/2;
    int midy=(ay+by)/2;
    recur(ax,ay,midx,midy);
    recur(midx+1,ay,bx,midy);
    recur(ax,midy+1,midx,by);
    recur(midx+1,midy+1,bx,by);
 
    printf(")");
 
}
 
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf(" %s",arr[i]);
    recur(0,0,n-1,n-1);
    return 0;
}