BOJ : 1992 쿼드트리

 

---

[BOJ 1992(S1) 리뷰]

 

전에 풀었던 별찍기 문제와 비슷해서 금방 풀었다.

SIZE와 X,Y좌표를 받아서 범위에대해 같은값인지 확인하고 같은값이 아니라면 크기를 줄여가며 재귀함수에 넣어주면 된다. 첨에 재귀함수를 실행하는 순서를 잘못넣어서 좀 틀렸지만 순서를 바로잡아주니 바로 정답처리 되었다.

 

---

 

#include <iostream>
#include <queue>
#include <string>
#include <string.h>
#include <math.h>
using namespace std;
char table[100][100];
int n;

int check(int size,int x, int y)
{
	char ret = table[x][y];
	for (int i = x; i < x + size; i++)
	{
		for (int j = y; j < y + size; j++)
		{
			if (table[i][j] != ret) //다름
				return -1;
		}
	}

	return ret;
}


void func(int size,int x,int y)
{
	int cur = check(size, x, y);
	if (cur != -1)
	{
		cout << cur-'0';
		return;
	}
	cout << '(';
	int n = size / 2;
	func(n,x,y); 
	func(n, x, y + n);
	func(n,x+n ,y );
	func(n, x + n, y + n);
	cout << ')';
}


int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(0);
	memset(table, ' ', sizeof(table));
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			cin >> table[i][j];
	}
	func(n, 0, 0);
}