[BAEKJOON] 1992번 : 쿼드트리

문 제

 

소 스  코 드

#include <iostream>
#include <string>
constexpr char WHITE		{ '0' };
constexpr char BLACK		{ '1' };


void QuadTree();
void Quad(std::string *, const int&, const int&, const int&);
bool CompareColor(std::string *, const int&, const int&, const int&);
void Display(const std::string * , const int & , const int & , const int & );


int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	QuadTree();
	
	return 0;
}

void QuadTree()
{
	int N;
	std::cin >> N;

	std::string *data{ new std::string[N] };
	
	for (int i = 0; i < N; ++i) {
		std::cin >> data[i];
	}

	Quad(data, N, 0, 0);
	
	delete[] data;
}

void Quad(std::string * arr, const int & n, const int & x, const int & y)
{
	//Display(arr, n, x, y);
	if (CompareColor(arr, n, x, y)) return;
	else {
		std::cout << '(';
		int num = n / 2;
		Quad(arr, num, x, y);				// 왼쪽 위
		Quad(arr, num, x, y + num);			// 오른쪽 위
		Quad(arr, num, x + num, y);			// 왼쪽 아래
		Quad(arr, num, x + num, y + num);	// 오른쪽 아래
		std::cout << ')';
	}
}

bool CompareColor(std::string * arr, const int & n, const int & x, const int & y)
{
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (arr[x][y] != arr[i + x][j + y]) return false;
		}
	}
	if (BLACK == arr[x][y])			std::cout << '1';
	else if (WHITE == arr[x][y])	std::cout << '0';

	return true;
}

void Display(const std::string * arr, const int & n, const int & x, const int & y) {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			std::cout << arr[x + i][y + j] << " ";
		}
		std::cout << '\n';
	}
	std::cout << "\n\n";
}

 

풀 이

 

순서에 맞게 재귀 함수를 통하여 구현 하였습니다.

 

출 력 값

 

 

문 제  출 처

문제 링크 : https://www.acmicpc.net/problem/1992

1992번: 쿼드트리