< 백준 BaekJoon : 1992번 쿼드트리 > C++

<< 문제 >>

 

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

1992번: 쿼드트리

 

 

쿼드트리는 영상이나 이미지 압축에 주로 사용되는 알고리즘입니다. 

 

4분면으로 나누어 흑/백을 판단하고 섞여있다면 다시 4분면으로 나누어 판단합니다.

 

듣기만 해도 재귀함수 생각이 절로나죠?

 

<< 코드 >>

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

int table[64][64];

void quadTree(int num, int y, int x){
	if (num == 1) { // 크기가 1인 경우는 바로 return 
		printf("%d", table[y][x]);
		return;
	}

	// 같은 색으로 이루어져있는지 확인 
	bool isWhite = false;
	bool isBlack = false;
	bool isClear = true;
	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++) {
			if (table[y + i][x + j] == 0) {
				isWhite = true;
			}
			else {
				isBlack = true;
			}
		}
	}

	if (isWhite && isBlack) { // 둘 다 true라는건 섞였다는 뜻
		isClear = false;
	}

	
	if (!isClear) { // 하나로만 이루어지지 않은 경우
		printf("%c", '(');
		quadTree(num / 2, y, x);
		quadTree(num / 2, y, x + num / 2);
		quadTree(num / 2, y + num / 2, x);
		quadTree(num / 2, y + num / 2, x + num / 2);
		printf("%c", ')');
	}
	else if (isWhite && !isBlack) { // 화이트만 있는 경우
		printf("%d",0);
	}
	else if (isBlack && !isWhite) { // 블랙만 있는 경우
		printf("%d", 1);
	}
	
}


int main() {
	int num;
	scanf("%d", &num);

	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++) {
			scanf("%1d", &table[i][j]);
		}
	}
	quadTree(num, 0, 0);
}

 

 

<< 깃헙 >> 

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%EB%B0%B1%EC%A4%80/Silver/1992.%E2%80%85%EC%BF%BC%EB%93%9C%ED%8A%B8%EB%A6%AC