[Baekjoon] 1992번: 쿼드 트리

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

1992번: 쿼드트리

 

---

 

문제 해결 과정

착안

주어진 데이터가 0 또는 1의 값으로 균일한지 판단하고, 균일하지 않다면 주어진 데이터를 4 개의 균등한 영역으로 나눈 다음 각각의 영역이 다시 0 또는 1의 값으로 균일한지 판단하는 분할 정복(divide and conquer) 알고리즘의 코드를 작성하여 문제를 해결하고자 했다.

 

구현

주어진 영역이 0 또는 1의 값으로 균일한 상태인지 판단하는 함수를 구현하여 활용하였고, 분할 정복 알고리즘에 따라 결과를 출력할 때 괄호를 출력하기 위한 명령줄의 위치에 유의하여 문제를 해결하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int Data[64][64];

bool IsHomogeneous(int x, int y, int len)
{
	for (int i = y; i < y + len; i++)
		for (int j = x; j < x + len; j++)
			if (Data[y][x] != Data[i][j])
				return false;

	return true;
}

void Partition(int x, int y, int len)
{
	int half = len / 2;
	if (IsHomogeneous(x, y, len))
		cout << Data[y][x];
	else
	{
		cout << "(";
		Partition(x, y, half);
		Partition(x + half, y, half);
		Partition(x, y + half, half);
		Partition(x + half, y + half, half);
		cout << ")";
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		char line[65] = { 0, };
		cin >> line;

		for (int j = 0; j < N; j++)
			Data[i][j] = line[j] == '1' ? 1 : 0;
	}

	Partition(0, 0, N);
	return 0;
}

 

실행 결과