[C/C++]백준 1992번 - 쿼드트리

 

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

1992번: 쿼드트리

문제

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

 

 

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다.  N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력

영상을 압축한 결과를 출력한다.

---

 

접근방식

 

분할 정복 문제가 그러하듯이 base case를 정의한 다음에, 문제를 부분문제로 나눈 후에 재귀 호출을 통해서 문제를 해결한다.  예를 들어서, 모든 칸들의 숫자가 0이면 결과값은 0이다.

아래와 같은 입력이 들어온 경우 결과는 0이다. 

 

0	0	0	0	0	0
0	0	0	0	0	0
0	0	0	0	0	0
0	0	0	0	0	0
0	0	0	0	0	0
0	0	0	0	0	0

첫번째 행부터 확인하면서 가다가 이전의 값과 다른 숫자를 만나면, 그 영역을 기점으로 4개의 영역으로 분할한다.

아래의 경우를 예를 들어보자. 모든 칸들의 숫자가 같지 않기 때문에, 4개의 역역으로 분할했다.

왼쪽 위부터 오른쪽 방향으로 영역의 이름을 순서대로 A,B,C,D라고 하겠다.

 

A영역의 경우 모든 칸들의 숫자가 0이므로, 16개의 칸 전체를 그냥 0 이라는 숫자 하나로 압축해서 표기할 수 있다.

 

B, C, D 영역의 경우에는 모든칸의 숫자가 같지 않으므로, 이야기가 달라진다. A영역을 제외한 나머지 영역에 대해서는

분할을 진행한다.

 

 

 

B영역만 따로 떼어서 관찰해보자.

B영역을 위에서 했던 것 처럼 4등분으로 분할한다. 각 영역들의 숫자들이 각각 같으므로,

왼쪽 위에서부터 차례대로 1001이라고 간단하게 표기할 수 있다.

나머지 영역도 같은 작업을 해 주면 된다.

 

 

B영역

 

각 영역은 괄호( )로 구별이 된다. 아래와 같이 분할이 되므로, 쿼드트리를 이용해서 압축해 본다면,

 

아래의 그림은 "( 0 (1 0 0 1) (1 0 0 0) (1 (1 0 1 1) 0 1) )" 이라고 할 수 있다.

 

 

지금까지 설명한 내용을 코드로 옮기면 다음과 같다.

 

 

코드

 

 

#include<cstdio>

char data[64][64];

void quadTree(int y, int x, int size)
{
	char head = data[y][x]; //기준이 되는 칸
	bool pass = true; //모든 칸들이 같은 경우 pass는 true
	int dx, dy;

	for (dy = 0; dy < size; dy++) {
		for (dx = 0; dx < size; dx++) {
        //칸들을 순회하다가 다른 숫자가 나오면, pass는 false
			if (head != data[y + dy][x + dx]) {
				pass = false;
				break;
			}
		}
        //위의 반복문을 돌다가 중간에 빠져나온 경우, 분할을 위해서 반복문을 빠져나옴.
		if (pass == false) break;
	}
	
    //모든 칸들의 숫자가 같다면, 하나의 문자로 출력
	if (pass) {
		printf("%c", head);
	}
    //칸을 순회하다가 다른 문자를 만나는 경우, 4등분으로 분할해서, 재귀 호출.
	else {
		int half = size / 2;

		printf("(");
		quadTree(y, x, half);
		quadTree(y, x + half, half);
		quadTree(y + half, x, half);
		quadTree(y + half, x + half, half);
		printf(")");
	}
}
int main()	
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%s", data + i);
	}

	quadTree(0, 0, n);

	return 0;
}

 

 

정석적인 분할정복 문제였다.

 

 

다른 문제의 코드 : https://github.com/DaeeYong/Algorithm-Solution-

DaeeYong/Algorithm-Solution-