백준 1992 쿼드트리

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

 

풀이

2630번 문제에서 입력과 출력부분을 수정 했다.

2630 : https://hydroponicglass.tistory.com/58

 

입력을 개별 정수를 라인으로 입력받도록 수정하고

4개로 분할을 시작할때 여는 괄호를, 분할을 끝날때 닫는 괄호를 출력한다.

또한 분할된 표는 각 셀을 전수조사해서 전부 0이면 0을 출력, 전부 1이면 1을 출력한다.

 

---

구현

//c++

#pragma warning (disable: 4996)

#include <iostream>
#include <cstdio>

int map[65][65];

void divide(int x1, int y1, int x2, int y2) {
	int zero = 0;
	int one = 0;
	for (int i = y1; i <= y2; i++) {
		for (int j = x1; j <= x2; j++) {
			if (map[i][j] == 1) one++;
			else zero++;
		}
	}

	if (zero == 0) { 
		std::cout << 1;
	}
	else if (one == 0) { 
		std::cout << 0;
	}
	else {
		std::cout << "(";
		divide(x1, y1, (x1+x2)/2, (y1+y2)/2); //1
		divide((x1+x2)/2+1, y1, x2, (y1+y2)/2); //2
		divide(x1, (y1+y2)/2+1, (x1+x2)/2, y2); //3
		divide((x1+x2)/2+1, (y1+y2)/2+1, x2, y2); //4
		std::cout << ")";
	}
	return;
}

int main() {
	int n;
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		char x[65];
		scanf("%s", &x);
		for (int j = 0; j < n; j++) map[i][j] = (int)x[j]-'0';
	}

	divide(0, 0, n-1, n-1);
}