[백준] 1992 C++ 쿼드트리(분할 정복)

- 문제 설명

 

- 문제 풀이

분할 정복을 활용해야하는 문제이다.

1. 검사하고자 하는 모든 영상(배열의 원소)들이 0만 있거나 1만 있으면 그 값만 출력하면 된다.

2. 만약 0과 1이 하나라도 섞여있으면 괄호 '(' 를 넣어 준 뒤 4개의 영역으로 재귀를 통해 분할하고, 그 뒤에 괄호 ')' 를 넣어준다.

3. 1, 2번을 반복한다.

 

ex1

1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1

예를 들면 이런 배열의 경우 1번 과정에서 끝이 나므로 답은 1이다.

 

 

ex2

 

이런 경우 1번 과정이 안되므로 2번 과정을 거쳐야 하므로 괄호를 넣어준 뒤 4개의 영역으로 분할하고 다시 검사한다.

answer : ()

 

 

 

왼쪽 아래의 영역은 모두 1이므로 더 이상 분할해 주지 않아도 된다. 나머지 영역은 다시 분할해줄 필요가 있다.

answer : ( () () 1 () )  [순서대로 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 괄호가 나온다. 왼쪽 아래는 출력을 해주면 끝이므로 괄호를 안해줘도 된다.]

 

 

 

 

왼쪽 위 - > 오른쪽 아래 영역을 제외한 모든 곳이 압축이 되었다.

answer : ( (110 () ) (0010) 1 (0001) )

 

 

 

 

더 이상 분할할 곳이 없으므로 과정은 여기서 마무리 된다.

answer : ( (1110 (0101) ) (0010) 1 (0001) )

 

- 코드

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

int N;
char arr[64][64]; // 입력값이 띄어쓰기 구분이 안돼있으므로 char로 선언
string ans = "";

void quad_tree(int x, int y, int size)
{
	char check = arr[x][y]; // 가장 왼쪽 위를 기준으로 비교
	for(int i = x; i < x + size; i++)
		for (int j = y; j < y + size; j++)
		{
			if (check == '0' && arr[i][j] == '1') 
				check = '2';
			if (check == '1' && arr[i][j] == '0')
				check = '2';

			if (check == '2')
			{
				ans += "(";
				quad_tree(x, y, size / 2); // 1/4 분면
				quad_tree(x, y + size/2, size / 2); // 2/4 분면
				quad_tree(x + size/2 , y, size / 2); // 3/4 분면
				quad_tree(x + size/2, y + size/2, size / 2); // 4/4 분면
				ans += ")";
				return;
			}
		}
	if (check == '0')
		ans += "0";
	else
		ans += "1";
}

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

	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> arr[i][j];

	quad_tree(0, 0, N);

	cout << ans;

	return 0;
}