백준 1992 - 쿼드트리

문제링크

• 백준 1992

문제설명

• 흰 점을 나타내는 0, 검은 점을 나타내는 1로만 이루어진 이차원 배열의 영상을 쿼드트리 압축으로 표현한다.
• 주어진 영상이 모두 0이면 “0”, 모두 1이면 “1”로 표현하고, 0과 1이 섞여 있으면 해당 영역을 4등분하여 각 영역에 같은 방법을 적용한다.

입력

• 첫째 줄에는 영상의 크기를 나타내는 숫자 N (2의 제곱수로 1~64)
• 길이 N의 문자열이 N줄에 걸쳐 들어온다. 문자열은 0 또는 1로 이루어져 있다.

문제접근방향(bokyoung)

1. 탐색 영역에 0과 1이 섞여 있는지 여부를 판단한다.
2. 0과 1이 섞여 있다면 현재 영역을 4개로 분할하는 재귀 호출을 한다.
   • 재귀호출을 시작할 때, “(“ 출력
   • 재귀호출을 빠져나올 때 “)” 출력
3. 0으로만 이루어져 있다면 “0”을 출력하고, 1로만 이루어져 있다면 “1”을 출력한다. (기저사례)
4. 위 과정을 재귀적으로 반복한다.

구현

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

// 탐색 영역이 단일 색(0 또는 1)인지, 혼합(2)인지 판단
char check_color(vector<string>& image, int x, int y, int n) {
	char ref = image[x][y];
	for (int r = 0; r < n; r++) {
		for (int c = 0; c < n; c++) {
			if (image[r+x][c+y] != ref)
				return '2';
		}
	}
	return ref;
}

void compress(vector<string>& image, int x, int y, int size) {
	// 기저사례: 영역이 0으로만 이루어졌거나 1로만 이루어진 경우
	char ref = check_color(image, x, y, size);
	if (ref == '0' || ref=='1') {
		cout << ref;
		return;
	}

	int half = size / 2;
	cout << "(";
	compress(image, x, y, half);
	compress(image, x, y + half, half);
	compress(image, x + half, y, half);
	compress(image, x + half, y + half, half);
	cout << ")";
	return;
}

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

	int N;
	string str;
	vector<string> image;
	cin >> N;
	for (int line = 0; line < N; line++) {
		cin >> str;
		image.push_back(str);
	}
	compress(image, 0, 0, N);
	return 0;
}