[c++] 백준 1992 쿼드트리

백준 단계별로 풀어보기 [분할 정복] 쿼드트리

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

1992번: 쿼드트리

 

[풀이]

앞서 풀었던 색종이 자르기 문제와 거의 유사하다. 0으로만 이루어져있으면 0을, 1로만 이루어져있으면 1을 문자열에 추가하고, 0과 1이 섞여있다면 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 재귀 호출을 한다. 재귀호출을 하는 코드 부문 앞, 뒤로 "(", ")"이 출력되도록 한다.

 

[코드]

#include <iostream>
#include <string>
#include <algorithm>

int arr[65][65];
std::string out;

void press(int y, int x, int size) {
	int check = arr[y][x];
	for (int i = y; i < y + size; i++) {
		for (int j = x; j < x + size; j++) {
			if (check == 0 && arr[i][j] == 1) {
				check = 2;
			}
			else if (check == 1 && arr[i][j] == 0) {
				check = 2;
			}

			if (check == 2) {
				out.append("(");
				press(y, x, size / 2); // 왼쪽 위
				press(y, x + size / 2, size / 2); // 오른쪽 위
				press(y + size / 2, x, size / 2); //왼쪽 아래
				press(y + size / 2, x + size / 2, size / 2); //오른쪽 아래
				out.append(")");
				return;
			}
		}
	}

	if (check == 0) {
		out.append("0");
	}
	else if (check == 1) {
		out.append("1");
	}
}

int main() {
	//쿼드 트리구조를 이용한 압축. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래
	int n;
	std::cin >> n;
	std::string str;

	for (int i = 0; i < n; i++) {
		std::cin >> str;
		for (int j = 0; j < n; j++) {
			arr[i][j] = str[j]-'0';
		}
	}

	press(0, 0, n);

	std::cout << out;
}