백준 1992번 : 쿼드트리 (C++)

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

1992번: 쿼드트리

 

 

코드

#include <iostream>
using namespace std;
char arr[64][64];
 
void func(int n,int x,int y)
{
    bool zero=true,one=true;
    for(int i=x;i<x+n;i++)
    {
        for(int j=y;j<y+n;j++)
        {
            if(arr[i][j]-'0'==0)
            {
                one=false;
            }
            if(arr[i][j]-'0'==1)
            {
                zero=false;
            }
        }
    }
    if(!one &&!zero) cout<<"(";
    if(one)
    {   cout<<1;
        return ;
    }
    else if(zero)
    {   cout<<0;
        return ;
    }
    else
    {
        func(n/2,x,y);
        func(n/2,x,y+n/2);
        func(n/2,x+n/2,y);
        func(n/2,x+n/2,y+n/2);
    }
    cout<<")";
    return ;
}
int main() {
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>arr[i][j];
        }
    }
   
    func(n,0,0);
    return 0;
}

풀이

 n이 주어지는데 n은 2의 제곱수이면서 1<=n<=64이다. n 행 n 열의 이차원 배열에 0 또는 1의 값을 입력받고 그 배열을 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래로 4등분한다. 각 부분이 모두 1이면 1을 출력하고 모두 0이라면 0을 출력한다. 4등분한 각 부분이 모두1이거나 모두 0이지 않으면 다시 그 부분을 4등분하고 위를 반복한다.

 func함수는 x 행 y 열에서 x+n 행 y+n 열까지의 원소가 모두 0인지, 모두 1인지 아니면 섞여 있는지를 검사한다. (8~21행) one이 true라면 1로만 이루어져 있는 것이고 zero가 true라면 0으로만 이루어져 있는 것이다. one,zero가 둘 다 false라면 섞여 있는 것이고 섞여 있다면 새로운 4등분을 만들어야 한다. 새로운 4등분을 표시해줄 여는 괄호 '('를 둘 다 false인 경우 출력해주고 1로만 이루어져 있다면 1을 출력,0으로만 이루어져 있다면 0을 출력, 둘 다 섞여 있다면 4등분으로 나누는 32~37행을 수행해준다. 그 후에 닫는 괄호를 출력한다.