[백준 1992] 쿼드트리

문제설명

알고리즘

1. 그래프 정보 입력 받기

2. 4등분 해서 해당 네모가 모두 같은 값으로 이루어진지 판단

3. 모두 같은 값이면 그 값을 출력하고 종료

4. 모두 같은 값이 아니면 또 4등분 해서 반복

코드

#include <iostream>
#include <string>
using namespace std;
int graph[65][65];

void cut(int a, int b, int size) {

	int cnt_0 = 0, cnt_1 = 0;
	for (int i = a; i < a + size; i++)//모두 1이거나 모두 0 인경우 판단
	{
		for (int j = b; j < b + size; j++)
		{
			if (graph[i][j])
				cnt_1++;
			else
				cnt_0++;
		}
	}
	if (!cnt_0 && cnt_1) {
		cout << 1;
		return;
	}
	else if (cnt_0 && !cnt_1) {
		cout << 0;
		return;
	}
	//4분할
		cout << "(";
		cut(a, b, size / 2);
		cut(a, b + size / 2, size / 2);
		cut(a + size / 2, b, size / 2);
		cut(a + size / 2, b + size / 2, size / 2);
		cout << ")";
	
}

int main() {
	int N;
	cin >> N;
	int cnt1 = 0, cnt0 = 0;
	for (int i = 0; i < N; i++)//값 입력 받기
	{
		string input;
		cin >> input;
		for (int j = 0; j < N; j++)
		{
			graph[i][j] = input[j] - '0';
		}
	}

	cut(0, 0, N);
}

고찰

처음에 문제를 이해하는게 쉽지 않아서 검색해서 뭘하라는 건지 이해했다

재귀를 통해서 푸는 문제인데, 테스트케이스는 맞는데 자꾸 틀렸다고 나왔다

이유는 알고보니 자른 단면이 전부 0이나 1로 되어있을 때 세고 값을 출력한 뒤, return 을 해줘야되는데 안해줘서 계속 틀린거였다

분할정복 문제는 알다가도 모르겠다

특히 재귀는 더 모르겠다