백준 1992 - 쿼드트리

문제 링크

쿼드트리를 실제로 구현을 해도 되지만, 굳이 트리를 만들지 않고 컨셉만 가져와서 재귀 함수로 해결할 수 있다.

#include <stdio.h>

int a[64][64] = {0,};

void count(int x1, int y1, int x2, int y2) {
    int f,x,y;
    f = 0;

    for (x=x1; x<x2 && !f; x++) {
        for (y=y1; y<y2 && !f; y++) {
            if (a[x][y] != a[x1][y1]) {
                f = 1;
                break;
            }
        }
    }

    if (f) { // need split
        printf("(");
        count(x1, y1, (x1+x2)/2, (y1+y2)/2);
        count((x1+x2)/2, y1, x2, (y1+y2)/2);
        count(x1, (y1+y2)/2, (x1+x2)/2, y2);
        count((x1+x2)/2, (y1+y2)/2, x2, y2);
        printf(")");
    } else {
        printf("%d", a[x1][y1]);
    }
}

int main() {
    int n,x,y;
    scanf("%d", &n);

    for (y=0; y<n; y++) {
        while ((getchar()) != '\n');
        for (x=0; x<n; x++) {
            a[x][y] = getchar() - '0';
        }
    }

    count(0,0,n,n);
    printf("\n");
    return 0;
}