1992 쿼드 트리

#include <stdio.h>
 
int n, q[64][64];
 
void tree(int x, int y, int size) {
    int pic = q[y][x];
    int same = true;
    for (int i = y; (i < y+size) && same; i++) { //위부터 아래까지 같으면 계속가고 틀리면 빠져나옴
        for (int j = x; (j < x+size) && same; j++) { //왼쪽부터 오른쪽까지
            if (pic != q[i][j]) { //배열의 x, y번째 비트랑 검사한 곳이랑 다르면 아래서 분할 
                same = false;
            }
        }
    }
 
    if (same) { //전부 다 1이거나 0이면 출력
        printf("%d", pic);
    }
    else { //아니면 분할
        printf("(");
        tree(x, y, size / 2); //왼쪽 위
        tree(x + (size / 2), y, size / 2); //오른쪽 위 
        tree(x, y + (size / 2), size / 2); //왼쪽 아래
        tree(x + (size / 2), y + (size / 2), size / 2); //오른쪽 아래 
        printf(")");
    }
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &q[i][j]);
        }
    }
    tree(0,0,n);
}

for문을 돌면서 i로 위부터 아래까지 같으면 계속 가고 틀리면 빠져나오고,

j로 왼쪽부터 오른쪽까지 돌면서 마찬가지로 틀릴 때까지 계속 간다.

배열의 x, y번째 비트랑 검사한 곳이랑 다르면 same을 false로 바꿔두고 계산은 아래서 한다.

같으면 개수를 세고 아니면 분할하는데 여기가 핵심 부분으로

size를 2로 나눈 값을 x, y에 더한다.

그렇게 나눠보면

왼쪽 위 x, y

오른쪽 위 x+(size/3), y

왼쪽 아래 x, y+(size/3)

오른쪽 아래 x+(size/3), y+(size/3)

로 나뉘며 각 조각마다 재귀를 돌려주면 된다.