[c++] 백준 #1992 쿼드트리

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

<풀이 방법>

이것 또한 분할정복 문제이다. 백준 1780 종이의 개수 문제를 풀었다면 아주 쉽게 한문제를 먹을 수 있다.

주어진 0, 1로만 이루어진 행렬을 4등분하였을 때 똑같은 숫자(all 0 or all 1)로만 이루어지지 않았다면 4등분하는 식으로 진행된다.

트리의 괄호는 4등분이 시작할 때마다 열어주고, 끝날 때 닫아주면 끝이다. 문제의 행렬이 공백없이 주어지니 getline을 쓰는 것을 잊지 말아야한다.(cin.ignore()은 덤!)

    #include <iostream>
    #include <string>
    #include <vector>
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h> 
    #include <string.h>
    #include <cstdio>
    #include <math.h>
    #include <map>
    #include <algorithm>
    #include <queue>
    #include <utility>
    using namespace std;
 
    int A[64][64];
    char str[65];
 
    bool cutornot(int a, int b, int size)
    {
        int pivot = A[a][b];
        for (int i=a;i<a+size;i++)
        {
            for (int j=b;j<b+size;j++)
            {
                if (pivot!=A[i][j]) return true;
            }
        }
        return false;
    }
 
    void divide(int a, int b,int cmp_size)
    {
        if (!cutornot(a,b,cmp_size))
        {
            cout << A[a][b];
        }
        else
        {
            cout << "(";
            cmp_size /= 2;
            for (int i=0;i<2;i++)
            {
                for (int j=0;j<2;j++)
                {
                    divide(a+cmp_size*i,b+cmp_size*j,cmp_size);
                    
                }
            }
            cout << ")";
        }
    }
 
    int main()
    {
        ios_base :: sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
        int N;
        cin >> N;
        int value = 0;
        cin.ignore();
        for (int i=0;i<N;i++)
        {
            str[0] = {0};
            cin.getline(str,N+1);
            for (int j=0;j<N;j++)
            {    
                A[i][j] = str[j] - '0';
            }
        }
 
        divide(0,0,N);
        
        return 0;
    }