[백준] 1992 쿼드트리 (C++)

 

문제 URL: https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

다음 문제는 N ×N 크기의 영상이 주어질 때, 이 영상을 쿼드트리로 압축한 결과를 출력하는 프로그램을 작성하는 문제로 처음 문제를 풀 때 문제에서 나타내는 말이 무엇인지 이해하는데 시간이 걸렸다. 결국 구글링을 해서 알아낸 문제이다. 

쿼드트리는 전체를 한번에 나타내지 못하면

왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래

이렇게 4개의 영역으로 나눠서 압축하는 것을 말한다.

 

위의 왼쪽 그림과 같이 영상이 주어졌을 때 먼저 이를 4등분하고 4등분한 영역이 0이나 1로 한번에 나타낼 수 있다면 0이나 1을 출력하고, 그렇지 않다면 그 영역을 다시 한번 4등분하여 계속 확인해 준다. 

따라서 dfs를 이용하여 코드를 작성하면 되는 문제이다. 

---

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

int N;
int MAP[MAX][MAX];

void DFS(int x, int y, int Size) {
	if (Size == 1) {
		cout << MAP[x][y];
		return;
	}

	bool OnlyZero, OnlyOne;
	OnlyZero = OnlyOne = true;
	for (int i = x; i < x + Size; i++) {
		for (int j = y; j < y + Size; j++) {
			if (MAP[i][j] == 0) 
				OnlyOne = false;
			if (MAP[i][j] == 1) 
				OnlyZero = false;
		}
	}

	if (OnlyZero == true) {
		cout << 0;
		return;
	}
	if (OnlyOne == true) {
		cout << 1;
		return;
	}

	cout << "(";
	DFS(x, y, Size / 2);
	DFS(x, y + Size / 2, Size / 2);
	DFS(x + Size / 2, y, Size / 2);
	DFS(x + Size / 2, y + Size / 2, Size / 2);
	cout << ")";
}

int main(void) {
	cin >> N;
	for (int i = 0; i < N; i++) {
		string S;
		cin >> S;
		// Map에 숫자 0 or 1 저장
		for (int j = 0; j < S.length(); j++)
			MAP[i][j] = S[j] - '0';  
	}

	DFS(0, 0, N);

	return 0;
}

참고: https://yabmoons.tistory.com/m/450