#1992번 쿼드트리 (C++)

링크 : www.acmicpc.net/problem/1992

1992번: 쿼드트리

문제를 이해하는데 시간이 다소 소요됐다.

문제 해석은 다음과 같으며, 아래의 그림을 이해하면 된다.

 

이 순서로 표기된다

 

문제 풀이는 다음과 같다.

1. 입력은 숫자가 아닌 문자로 진행된다. 

2. 문자를 그대로 받아도 되고, 숫자로 바꿔서 진행해도 된다. 

본인은 둘 다 진행했으나, 편의상 문자를 그대로 받아 진행하겠다. 

3. 재귀를 통해 1번부터 마지막 번호까지 재귀함수를 진행한다. 

4. 지정된 영역의 범위를 모두 세어봤을 때, '0'의 갯수나 '1'의 갯수가 0개일 경우 압축이 진행된다. 

5. 만약 두 종류의 갯수가 0개가 아닐 경우, 괄호를 추가해주고

영역을 네 분할로 나누어 다시 재귀함수를 호출한다.

 

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

int n = 0;
char arr[65][65];
string ans = "";

void check(int starty, int startx, int endy, int endx) {
	int b = 0, w = 0; // b = 1로 표시된 구역
	for (int i = starty; i <= endy; i++) {
		for (int j = startx; j <= endx; j++) {
			if (arr[i][j] == '1') b++;
			else w++;
		}
	}
	if (b == 0 || w == 0) {
		if (b == 0) ans += "0";
		else ans += "1";
	}
	else {
		ans += "(";
		check(starty, startx, (starty+endy) / 2, (startx+endx) / 2); // 1사분면
		check(starty, (startx+endx)/2+1,(starty+endy)/2,endx); // 2사분면
		check((starty+endy)/2+1, startx, endy, (startx+endx)/2); // 3사분면
		check((starty + endy) / 2 + 1, (startx + endx) / 2 + 1, endy, endx); //4사분면
		ans += ")";
	}
}

int main() {
	ios::sync_with_stdio(NULL);
	cin.tie(NULL);
	char c;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> c;
			arr[i][j] = c;
		}
	}
	check(1, 1, n, n);
	cout << ans << "\n";
	return 0;
}

아래는 문자를 숫자로 변형, 위는 문자를 그대로 문자값으로 저장한 답변

 

문제만 잘 이해됐다면 그다지 어렵지 않다. 

#2630번 색종이 만들기의 확장판이다.