[백준 1992 - C++] 쿼드트리

⬇️ 문제 출처

백준 1992 : 쿼드트리

💡 접근 방법

분할정복이구나!

✏️ 풀이

문제를 읽고, 분할 정복이라는 것을 직감했다.
어떤 구간의 배열이 모두 같은 숫자로 이루어져 있으면, 압축 결과를 출력하고, 0과 1이 섞여있으면, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영역으로 분할해 같은 숫자로 이루어져 있을 때까지 재귀를 했다. 재귀 함수의 인자로는 (왼쪽 위의 y좌표, 왼쪽 위의 x좌표, 오른쪽 아래의 y좌표, 오른쪽 아래의 x좌표, 왼쪽 위의 영상 값)을 주었다. 그리고 만약 4개의 영역으로 압축하게 될 때는, 재귀를 호출하기 전, '('를 출력하고, 4개의 영역으로 분할된 재귀를 모두 호출한 후에 ')'를 출력함으로써 4개의 영역을 압축한 결과를 표현해 줬다.

⌨️ 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <string>
#include <queue>
#include <cstring>
#include <tuple>
#include <cmath>
#include <math.h>
#define MAX_N 1000+5
#define endl "\n"
const int INF = 987654321;
typedef long long ll;
using namespace std;
int map[64 + 5][64 + 5];
void div(int top_y, int top_x, int down_y, int down_x, int num) {
	bool flag = false;
	for (int i = top_y; i <= down_y; i++) {
		for (int j = top_x; j <= down_x; j++) {
			if (map[i][j] != num) {
				flag = true;
				break;
			}
		}
		if (flag) break;
	}

	if (flag) {
		int mid_y = (top_y + down_y) / 2;
		int mid_x = (top_x + down_x) / 2;
		cout << "(";
		div(top_y, top_x, mid_y, mid_x, map[top_y][top_x]);
		div(top_y, mid_x + 1, mid_y, down_x, map[top_y][mid_x + 1]);
		div(mid_y + 1, top_x, down_y, mid_x, map[mid_y + 1][top_x]);
		div(mid_y + 1, mid_x + 1, down_y, down_x, map[mid_y + 1][mid_x + 1]);
		cout << ")";
	}
	else {
		cout << num;
	}
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int N; cin >> N;
	for (int i = 1; i <= N; i++) {
		string s; cin >> s;
		for (int j = 1; j <= s.length(); j++) {
			map[i][j] = s[j - 1] - '0';
		}
	}
	bool flag = false;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (map[i][j] != map[1][1]) {
				flag = true;
				break;
			}
		}
		if (flag) break;
	}
	
	if (flag) {
		int mid = (1 + N) / 2;
		cout << "(";
		div(1, 1, mid, mid, map[1][1]);
		div(1, mid + 1, mid, N, map[1][mid + 1]);
		div(mid + 1, 1, N, mid, map[mid + 1][1]);
		div(mid + 1, mid + 1, N, N, map[mid + 1][mid + 1]);
		cout << ")";
	}
	else {
		cout << map[1][1];
	}
    return 0;
}

🔥🔥🔥

야호!