BAEKJOON 1992 - 쿼드트리

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

분할정복 문제입니다. 시작점과 크기를 인수로 받아 해당 영역이 모두 같은지 확인을 한 후 같지 않다면 4 구역으로 분할해 재귀 호출을 하여 풀어봤습니다.

#pragma warning (disable:4996)
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
 
using namespace std;
 
int n;
bool tree[65][65];
 
void compress(int startY, int startX, int size)
{
    bool start = tree[startY][startX];
    bool isSame = true;
    for (int y = startY; y < startY + size; y++)
    {
        for (int x = startX; x < startX + size; x++)
        {
            if (tree[y][x] != start)
            {
                isSame = false;
                break;
            }
        }
        if (!isSame)
            break;
    }
    if (isSame)
    {
        printf ("%d", start);
    }
    else
    {
        printf("%c", '(');
        int newSize = size / 2;
        compress(startY, startX, newSize);
        compress(startY, startX + newSize, newSize);
        compress(startY + newSize, startX, newSize);
        compress(startY + newSize, startX + newSize, newSize);
        printf("%c", ')');
    }
    
}
 
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            char c;
            scanf(" %c", &c);
            tree[i][j] = c - '0';
        }
    }
    compress(0, 0, n);
    return 0;
}