[Baekjoon/백준] 1992번: 쿼드트리(C/C++)

단계별로 풀어보기 20단계(분할 정복) 2번 문제

https://www.acmicpc.net/step/20

분할 정복 단계

---

백준 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의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

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

---

접근 방법

이번 문제는 영상 크기 N을 입력받고 NxN 크기의 영상을 0과 1로 구분해 입력받아서 영상 압축 결과를 출력하는 문제다. 영상 압축은 지난 문제인 색종이 만들기와 비슷하게 영상을 정사각형으로 봤을 때 해당 범위 내 숫자가 모두 0이거나 모두 1일때, 0 혹은 1을 출력하면 된다. 단, 나눴을때는 괄호로 구분해주어야한다.

이전 문제풀이와 마찬가지로 이중 배열을 사용해도 되고, 아니면 작성한 코드처럼 string 배열을 사용해서 함수를 반복해서 진행해도 된다.

함수는 정사각형의 첫값을 저장해서 이중 반복문으로 해당 숫자와 같은지 다른지 확인해서, 다른 값이 있다면 괄호를 출력하고 정사각형을 4등분해서 재귀 함수 형태로 다른 값이 없을때까지 반복하게 하면 된다. 만약 다른 값이 없다면, 첫 값이 압축한 결괏값이 되므로 이를 출력하게 만들면 문제를 해결할 수 있다.

---

코드

#include <iostream>
#include <string>
using namespace std;
#define MAX 64

string movie[MAX];

void slice(int x, int y, int N) {
	char temp = movie[x][y];

	for (int i = x; i < x + N; i++)
		for (int j = y; j < y + N; j++)
			if (movie[i][j] != temp) {
				cout << "(";
				slice(x, y, N / 2);
				slice(x, y + N / 2, N / 2);
				slice(x + N / 2, y, N / 2);
				slice(x + N / 2, y + N / 2, N / 2);
				cout << ")";
				return;
			}

	cout << temp;
}

int main(int argc, char *argv[]) {
	int N;
	cin >> N;

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

	slice(0, 0, N);
	cout << endl;

	return 0;
}

---

결과

백준 제출 결과