백준 - 1992 쿼드트리

[문제 링크]

0과 1로되어있는 데이터를 쿼드트리로 압축하는 문제이다.

문제 해결 방법은 다양한데, 분할 정복으로 푼다는 점에선 모두 일치한다.

해결방법 중 하나는 그냥 전부 분할해서, 반환 받은 값이 모두 일치하면 하나로 출력하고, 다르면 나눠 출력하는 방법이 있고.

또 하나는 검사해 나가면서 하나라도 다른 값이 있으면 분할하는 방법이 있다.

나는 두 번째 방법으로 해결하였다. 밑은 이를 구현한 코드이다.

#include <cstdio>
int N, input[64][64];
void quadTree(int x, int y, int size) {
    int cur = input[y][x];
    bool flag = true;
    for (int i = y; (i< y + size) && flag; i++) 
        for (int j = x; (j<x + size) && flag; j++) 
            if (cur != input[i][j]) flag = false;
    //전부 일치했으면 초기 문자 출력 
    if (flag) printf("%d", cur);
    //아니면 4개로 분할한다. 
    else {
        printf("(");
        quadTree(x, y, size / 2);
        quadTree(x + size / 2, y, size / 2);
        quadTree(x, y + size / 2, size / 2);
        quadTree(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", &input[i][j]);
    quadTree(0, 0, N);
}