[C++] 백준 1992번: 쿼드트리

www.acmicpc.net/problem/1992

1992번: 쿼드트리

분할 정복의 대표격인 문제인 쿼드 트리이다.

 

예전에 프로그래머스 월간 챌린지에서 비슷한 문제가 나온적이 있었다. 그땐 개념을 제대로 몰라 막 풀었는데 이번에는 재귀를 사용해서 푸는 법을 알게 되어 이를 사용해 풀 수 있었다.

 

괄호를 넣어줘야되는 부분이 좀 까다로워서 고민을 많이 했는데 함수 호출전에 미리 넣어주는 방식으로 해결할 수 있었다.

 

이전에 Z라는 문제를 풀었는데 그때 답지를 보며 공부한 것이 크게 도움되었다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int N;
int quad[65][65];
string ans;

void dfs(int x, int y, int z) {
	int check = 0;
	for (int i = x; i < x + z; i++) {
		for (int j = y; j < y + z; j++) {
			if (quad[x][y] != quad[i][j]) {
				check = 1;
				break;
			}
		}
	}
	if (check == 0) {
		ans += to_string(quad[x][y]);
	}
	else {
		z = z / 2;
		ans += "(";
		if (z == 1) {
			ans += to_string(quad[x][y]);
			ans += to_string(quad[x][y + 1]);
			ans += to_string(quad[x + 1][y]);
			ans += to_string(quad[x + 1][y + 1]);
		}
		else {
			dfs(x, y, z);
			dfs(x, y + z, z);
			dfs(x + z, y, z);
			dfs(x + z, y + z, z);
		}
		ans += ")";
	}
	return;
}

int main() {
	int c = 0;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%1d", &quad[i][j]);
		}
	}
	dfs(0, 0, N);
	cout << ans;
	return 0;
}