백준 1992번: 쿼드트리 (C++)

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

1992번: 쿼드트리

 

풀이

분할 정복 문제인걸 바로 알았지만 항상 분할 정복, 재귀는 머리가 아프다.

 

partition 함수를 호출하면 시작부터 끝부분 중에 하나라도 다른 숫자가 있으면 chk 를 false 로 바꿔주었고

false 일 때 4개로 분할해서 재귀를 호출하고

true 일 때 숫자를 저장했다.

 

괄호 없이 출력하는 건 쉬웠는데 괄호를 어떻게 출력시켜주어야할 지 고민하는 과정이 오래걸렸다.

 

string 의 append 를 이용해 재귀 함수 호출 시작과 끝에 ' ( ' 와 ' ) ' 를 넣어주었다.

 

 

전체 코드

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int N;
int arr[65][65] = { 0, };
string ans;

void partition(int left, int right, int n) {
	bool chk = true;

	for (int i = left; i < left + n; i++) {
		for (int j = right; j < right + n; j++) {
			if (arr[left][right] != arr[i][j]) chk = false;
		}
	}

	if (!chk) {
		ans.append("(");
		partition(left, right, n / 2);
		partition(left, right + n / 2, n / 2);
		partition(left + n / 2, right, n / 2);
		partition(left + n / 2, right + n / 2, n / 2);
		ans.append(")");
	}
	else {
		ans.append(to_string(arr[left][right]));
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N;

	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < N; j++) arr[i][j] = s[j] - '0';
	}

	partition(0, 0, N);
	cout << ans;
}