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

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

1992번: 쿼드트리

예전에 풀어봤던 분할 문제하고 비슷해서 금방 풀었다.

1.n*n 크기의 사각형을 검사한다.

2.전부 0이거나 1이면 문자열에 0이나 1을 추가해준다.

3. 아니면 문자열에 (을 추가하고  n/2*n/2 크기의 사각형 4개로 분할해서 사각형을 검사한다.

4. 분할한 사각형을 다 검사하면 )을 문자열에 추가한다.

*입력이 문자열로 들어오기 때문에 잘라서 int로 바꿔서 배열에 넣어줘야한다.

*배열안에 다른 값이 한 개라도 있으면 분할 해야하기때문에 배열의 한 값하고 다른 값을 비교하는 것보다

0과 1의 개수를 세어줘서 각각 n*n개인 것을 검사하는 방식으로 했다.

 

#include <iostream>
#include<string>

using namespace std;

int N;
int image[64][64];
int zero, one;
string s="";
void QuadTree(int x,int y,int n)
{
	//cout << s << endl;
	if (n == 0)
		return;
	zero = 0; one = 0;
	for(int i=x;i<x+n;i++)
		for (int j = y; j <y+n; j++)
		{
			if (image[i][j])
				one++;
			else
				zero++;
		}
	if (one == n * n)
	{
		s += "1";
	}
	else if (zero == n * n)
	{
		s += "0";
	}
	else
	{
		s += "(";
		QuadTree(x,y, n / 2);
		QuadTree(x, y + n / 2, n / 2);//0 4 4
		QuadTree(x + n / 2, y ,n / 2);
		QuadTree(x + n / 2, y + n / 2, n / 2);
		s += ")";


	}

}

int main()
{
	cin >> N;
	string temp;
	for (int i = 0; i < N; i++)
	{
		cin >> temp;
		for (int j = 0; j < N; j++)
		{
			image[i][j] = temp[j]-'0';
		
			
		}
	}
	//s += "(";
	QuadTree(0,0, N);
	cout << s;

}