4) 백준 1992 - 쿼드트리

1992번: 쿼드트리 (acmicpc.net)

1992번: 쿼드트리

---

분할 정복문제.

관건은 괄호를 어떻게 처리할까 였다.

#include <bits/stdc++.h>

using namespace std;

char video[64][64];
string answer = "";

void quadTree(int N, int x, int y) {
	int cnt = 0;
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			if(video[x + i][y + j] == '1') {
				cnt++;
			}
		}
	}
	if(cnt == N*N) {
		answer += "1";
	}
	else if(cnt == 0) {
		answer += "0";
	}
	else {
		answer += "(";
		quadTree(N/2, x, y);
		quadTree(N/2, x, y+ N/2);
		quadTree(N/2, x + N/2, y);
		quadTree(N/2, x + N/2, y + N/2);
		answer += ")";
	}
}

int main(void) {
	int N;
	cin >> N;
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			cin >> video[i][j];
		}
	}
	quadTree(N, 0, 0);
	
	cout << answer << endl;
}

닫는 괄호는 분할이 다 끝나면 닫아주기만 해서 문제 없었는데 여는 괄호를 어디다 둘까 고민을 했다.

[ 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고 ] 이 문장에서 힌트를 얻었다.

여는 괄호는 흑백영상을 나눌때만 열어주면 된다.