[BAEKJOON] 1992번 쿼드트리

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

1992번: 쿼드트리

 

이 문제를 보자 마자 생각이 든 문제는 별 찍기 문제였다.

2024.03.10 - [Algorithm/DFS] - [BAEKJOON] 2448번 별 찍기 - 11

[BAEKJOON] 2448번 별 찍기 - 11

같은 모양이 반복되면서 프랙탈 구조를 보여서 접근하기 정말 쉬웠다.

그리고 이 문제는 정사각형에서 4등분한 각 구역이 0 이나 1중 하나의 숫자로 표현할 수 없으면 표현할 수 있을때 까지 4등분으로 분할 하는 것을 반복한다. 그리고 재귀 함수의 기준은 왼쪽위 좌표로 잡았다. 

• 무슨 기준으로 재귀 함수를 구현하는가? 왼쪽 위 좌표와, 한 변의 길이
• 괄호()는 어떻게  표현하는가? 어차피 4개기준으로 괄호가 짝지어서 하나씩 있어야하므로 4등분으로 나누어 재귀적으로 탐색하기전에 먼저 괄호를 열고 한 depth에서 4개의 부분이 모두 탐색이 끝나면 괄호를 닫는다.

 

#include <iostream>

using namespace std;
int n, map[65][65];

void dfs(int y, int x, int len) {
	if (len == 1) {
		cout << map[y][x];
		return;
	}

	bool one = true, zero = true;

	for (int i = y; i < y + len; i++) {
		for (int j = x; j < x + len; j++) {
			if (map[i][j]) zero = false;
			else one = false;
		}
	}
	// 성공했을 경우 더 깊이 탐색할 필요 X
	if (one == true) {
		cout << 1;
		return;
	}

	if (zero == true) {
		cout << 0;
		return;
	}
	cout << "(";
	dfs(y, x, len / 2);
	dfs(y, x + len / 2, len / 2);
	dfs(y + len / 2, x, len / 2);
	dfs(y + len / 2, x + len / 2, len / 2);
	cout << ")";
}


int main(){
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < n; j++) {
			map[i][j] = s[j] - '0';
		}
	}
	dfs(0, 0, n);
}

 

알고리즘적으로 딱히 어려운 것은 없었지만, 기준을 정하는데 조금 시간이 소요 됐다.