[BOJ]1992-쿼드 트리

1992

헤딩 코드

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

vector<vector<int>> board;

string QuadTree(pair<int, int> firstIndex, pair<int, int>secondIndex, pair<int, int>thirdIndex, pair<int, int>lastIndex)
{
	cout << secondIndex.first << ' ' << secondIndex.second << endl;
	if (firstIndex.first - secondIndex.first == 1)
	{
		int num1 = board[firstIndex.first][firstIndex.second];
		int num2 = board[secondIndex.first][secondIndex.second];
		int num3 = board[thirdIndex.first][secondIndex.second];
		int num4 = board[lastIndex.first][lastIndex.second];


		if (num1 == num2 && num1 == num3 && num1 == num4)
		{
			return to_string(num1) ;
		}
		// 가장 작은 구역
		return '(' + to_string(num1) + to_string(num2) + to_string(num3) + to_string(num4) +')';
	}

	int amount = secondIndex.first - firstIndex.first;
	amount /= 2;

	string res1 = QuadTree(firstIndex, { firstIndex.first, firstIndex.second + amount }, { firstIndex.first + amount, firstIndex.second }, { firstIndex.first + amount, firstIndex.second + amount });
	string res2 = QuadTree(secondIndex, { secondIndex.first, secondIndex.second + amount }, { secondIndex.first + amount, secondIndex.second }, { secondIndex.first + amount, secondIndex.second + amount });
	string res3 = QuadTree(thirdIndex, { thirdIndex.first, thirdIndex.second + amount }, { thirdIndex.first + amount, thirdIndex.second }, { thirdIndex.first + amount, thirdIndex.second + amount });
	string res4 = QuadTree(lastIndex, { lastIndex.first, lastIndex.second + amount }, { lastIndex.first + amount, lastIndex.second }, { lastIndex.first + amount, lastIndex.second + amount });

	if (res1  == res2 && res1 == res3 && res1 == res4)
	{
		return res1;
	}
	// 가장 작은 구역
	return '(' + res1 + res2 + res3 + res4 + ')';
}



int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		vector<int> v;
		int tmp;
		cin >> tmp;
		for (int j = 0; j < N; j++)
		{
			v.insert(v.begin(), tmp % 10);
			tmp /= 10;
		}

		board.push_back(v);
	}

	int half = N / 2;

	cout << QuadTree({0,0},{0, half},{half , 0},{half, half});
}

4부분의 시작 인덱스를 pair로 받는 방법을 생각했는데 코드가 너무 복잡하고 예제도 통과하지 못해 풀이를 찾아보았다.

결과 코드

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

vector<vector<int>> board;

void QuadTree(int size, int x, int y)
{
	
	if (size == 1)
	{
		cout << board[x][y];
		return;
	}
	bool zeroflag = true;
	bool oneflag = true;
	for (int i = x; i < x + size; i++)
	{
		for (int j = y; j < y + size; j++)
		{

			if (board[i][j])
			{
				zeroflag = false;
			}
			else
			{
				oneflag = false;
			}
		}
	}
	if (zeroflag)
	{
		cout << 0;
	}
	else if (oneflag)
	{
		cout << 1;
	}
	else
	{
		cout << "(";
		QuadTree(size / 2, x, y);
		QuadTree(size / 2, x, y + size / 2);
		QuadTree(size / 2, x + size / 2, y);
		QuadTree(size / 2, x + size / 2, y + size / 2);
		cout << ")";
	}
}



int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		vector<int> v;
		string tmp;
		cin >> tmp;
		for (int j = 0; j < N; j++)
		{
			v.push_back(tmp[j] - '0');
		}
		board.push_back(v);
	}
	
	QuadTree(N, 0, 0);
}

해당 분할 구간에서 0과 1을 확인한 후 맞는 경우 압축하고, 아닌 경우 분할을 한 번 더 진행한다.

이전과의 차이점은 분할을 할 때 조건을 통과하는 것.

참고자료

---

1992 쿼드 트리 c++ 풀이