쿼드 트리 이문제는 다시 복습 해주어야 한다.

이문제 출력결과 보고 한참을 생각했다.

이거를 보고 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 4개의 영상으로 압축을 한다는 말로

"(0(0011)(0(0111)01)1)" 이거를 이해할려고 하니까 도대체 무슨말인지 1도 이해가 안갔다.

"강의"듣고 문제 바로 이해함.

먼저 현재 8 by 8 이니까

4by4씩 정사각형으로 4등분 한다. 왼쪽 4x4는 싹다 0이니까

(0

그다음에 오른쪽 위 4x4를 2x2로 4개로 쪼개서 본다. 그러면 0011

(0(0011)

이런식으로 가는 거임 ㅇㅋ?

재귀함수 ❗

똑같은 행위가 반복될 때,

인자는 수정이 되지만 베이스 로직은 같을 때, 재귀함수를 사용을 한다.

문제를 보면은

이런식으로 탐색영역만 다르지 로직은 같다.

이런식으로 분할정복을 할 것인데, 재귀함수는 기저사례와 메인로직으로 나뉜다.

그럼 기저사례에는 뭐가 들어가야하나?

바로 size()가 1일 경우가 아니겠나?

재귀함수 흐름 다시 보기

이런식으로 문어발 식으로 퍼져나갈 것이다.

그러다가 결국에는

이런식으로 return 값이 있을 것이다.

string 생성자 ❓

https://www.techiedelight.com/ko/convert-char-to-string-cpp/

여기 함 보도록 하자.

x1, x2, y1, y2

x1, x2, y1, y2 이런식으로 좌표 잡는거보다

size로 접근하는게 더 쉽다.

cpp 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
#define endl "\n"

int n;
string s;
char a[101][101];

string go(int y, int x, int size)
{
	cout << y << " , " << x << " , " << size << endl;

	if (size == 1) return string(1, a[y][x]);

	char b = a[y][x];
	string ret = "";

	for (int i = y; i < y + size; ++i)
	{
		for (int j = x; j < x + size; ++j)
		{
			if (b != a[i][j])
			{
				ret += '(';
				ret += go(y, x, size / 2);
				ret += go(y, x + size / 2, size / 2);
				ret += go(y + size / 2, x, size / 2);
				ret += go(y + size / 2, x + size / 2, size / 2);
				ret += ')';
				return ret;
			}
		}
	}
	return string(1, a[y][x]);
}

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

	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> s;
		for (int j = 0; j < n; ++j)
			a[i][j] = s[j];
	}

	cout << go(0, 0, n) << endl;
	
	return 0;
}

코드 분석

재귀함수가 이해가 안간다면은

이렇게 분석을 하는게 좋다.

처음에 좌상단을 보면은

1111
1111
0001
0001 이기때문에

'(' 로 일단 시작한다음에

다시 '('로 시작한다.

그러면 일단 '((' 인 상태에서

'((110'으로 시작하다가 y = 2, x = 2인 경우 size가 1인 경우로 go를 호출해서

'(0101)'이라는 문자열이

'((110'뒤에 붙으면

'((110(0101)'이렇게된다. 이까지가

밑줄 그은 부분까지임.

그리고 우상단은 16개가 다 같지는 않기 때문에 2칸씩으로 쪼개는 부분 들어가게되면은 (0010)으로 나오게 되는데 그부분을

'((110(0101)'여기에 붙인다.

'((110(0101)' 이렇게됨.

그리고 좌하단은 싹다 1이라서 '1'을 붙인다.

'((110(0101)1'

그리고 우하단은

0000
0000
0011
0011

이기때문에 2칸씩 쪼개면은

(0001)이 된다.

'((110(0101)1(0001)' 이 최종답이다.