BOJ 1992번 쿼드트리

BOJ : https://www.acmicpc.net/problem/1992

github : https://github.com/junho0956/Algorithm/blob/master/1992/1992/%EC%86%8C%EC%8A%A4.cpp

 

이전에 풀었던 BOJ 1780번 종이의 개수와 같은 문제이다.

/2 씩 해가면서 분할하여 확인하면된다.

 

#include <cstdio>
using namespace std;
#pragma warning(disable:4996)
int arr[64][64];
 
void quadTree(int N, int y, int x) {
    bool test = true;
    for (int i = y; i < y + N; i++) {
        for (int k = x; k < x + N; k++) {
            if (arr[i][k] != arr[y][x]) {
                test = false;
                break;
            }
        }
        if (!test) break;
    }
 
    if (test) printf("%d",arr[y][x]);
    else {
        printf("(");
        int div = N / 2;
        for (int i = 0; i < 2; i++) {
            for (int k = 0; k < 2; k++) {
                quadTree(div, y + i * div, x + k*div);
            }
        }
        printf(")");
    }
}
 
int main() {
    int N; scanf("%d",&N);
 
    for (int i = 0; i < N; i++)
        for (int k = 0; k < N; k++)
            scanf("%1d", &arr[i][k]);
 
    quadTree(N, 0, 0);
    return 0;
}