04.05. 쿼드트리[Divide and conquer][백준 1992]

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

1992번: 쿼드트리

 

Algorithm classification : Divide and conquer, Recursion

 

04.05.1. Problem

There is a method called a quad tree as a data structure that compresses and expresses black and white images. In an image (two-dimensional array) consisting of only 0s representing white points and 1s representing black points, if many points of the same number are clustered in one place, it can be expressed simply by compressing them in a quad tree.

If the given image is all 0s, the compression result becomes "0", and when all the given images are all 1s, the compression result becomes "1". If 0 and 1 are mixed, the entire image cannot be displayed at once, and it is divided into four images: upper left, upper right, lower left, lower right, and compressed. tied inside

In the figure above, the image on the left is given as a number as in the arrangement on the right, and when this image is compressed using a quad tree structure, it is expressed as "(0(0011)(0(0111)01)1)". Given an image of size N × N, write a program that outputs the compressed result of this image.

 

04.05.2. Input limit

The first line is given a number N representing the size of the image. N is always given as a power of 2 and has the range 1 ≤ N ≤ 64. From the second line, N strings of length N are entered. Each character string consists of a number of 0 or 1 and represents each point of the image.

 

04.05.3. Output

Outputs the compressed image.

 

04.05.4. Solution

 이 문제도 유명한 문제 중 하나입니다. 앞서 포스팅한 종이의 개수 문제와 유사하죠. 출력하는 순서만 조심하시면 됩니다.(즉, 분할 후 어떤 순서로 부분문제를 풀어나갈지 고민하셔야 합니다.)

void cal(int c_x, int c_y, int size){
	c = 0;
	if(size == 1){
		printf("%d",datab[c_x][c_y]);
		return;
	}
	for(i = c_x; i < c_x + size; i++){
		for(j = c_y; j < c_y + size; j++){
			if(datab[c_x][c_y] != datab[i][j]){
				c++;
			}
		}
	}
	if(c == 0){
		printf("%d",datab[c_x][c_y]);
		return;
	}
	printf("(");
	cal(c_x, c_y, size/2);
	cal(c_x, c_y+size/2, size/2);
	cal(c_x+size/2, c_y, size/2);
	cal(c_x+size/2, c_y+size/2, size/2);
	printf(")");
}

 

	cal(1, 1, n);