BOJ 1992 쿼드트리

www.acmicpc.net/problem/1992

1992번: 쿼드트리

색종이 문제랑 똑같은데 왜 랭크는 높은지 1도 이해할 수 없는 문제다. 똑같이 풀었다. 아니 사실 다른 점이 있긴 한데, 그냥... 내가 자른 것이 내 생각대로 잘리진 않아서 코드 한 60번째 줄 보면 2랑 3이랑 바뀌어있을거다. 그거다. 확인해보고 싶으면 출력하면 된다.

#include <iostream>
#include <vector>
using namespace std;

int check(vector<vector<int>> paper, int size);
string quadTree(vector<vector<int>> paper, int size);

int main()
{
	int size;
	cin >> size;
	vector<vector<int>> paper(size);
	for (int i = 0; i < size; i++)
	{
		paper[i] = vector<int>(size);
		string tmp;
		cin >> tmp;
		for (int j = 0; j < size; j++)
		{
			paper[i][j] = tmp[j] - 48;
		}
	}
	cout <<  quadTree(paper, size) ;
	return 0;
}

string quadTree(vector<vector<int>> paper, int size)
{
	
	int tmp = check(paper, size);
	if (tmp != 2)
	{
		if (tmp == 0)
		{
			return "0";
		}
		else
		{
			return "1";
		}
	}
	else
	{
		vector<vector<int>> p1(size / 2), p2(size / 2), p3(size / 2), p4(size / 2);
		for (int i = 0; i < size / 2; i++)
		{
			p1[i] = vector<int>(size / 2);
			p2[i] = vector<int>(size / 2);
			p3[i] = vector<int>(size / 2);
			p4[i] = vector<int>(size / 2);
			for (int j = 0; j < size / 2; j++)
			{
				p1[i][j] = paper[i][j];
				p2[i][j] = paper[i + size / 2][j];
				p3[i][j] = paper[i][j + size / 2];
				p4[i][j] = paper[i + size / 2][j + size / 2];
			}
		}
		string a1 = quadTree(p1, size / 2);
		string a3 = quadTree(p2, size / 2);
		string a2 = quadTree(p3, size / 2);
		string a4 = quadTree(p4, size / 2);
		return "(" + a1 + a2 + a3 + a4 + ")";
	}
}

int check(vector<vector<int>> paper, int size)
{
	int cnt = 0;
	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < size; j++)
			cnt += paper[i][j];
	}
	if (cnt == 0)
	{
		return 0;
	}
	else if (cnt == size * size)
	{
		return 1;
	}
	else
		return 2;
}