[Week 2] QUADTREE self review - hanjuuuuuu

[hanjuuuuuu]

QUADTREE self review

1. 해결 시도 과정

쿼드트리 전체를 뒤집기 위해서는 왼쪽상단, 오른쪽상단, 왼쪽하단, 오른쪽하단 네부분으로 나누고, 이 안에서 더 많이 나뉘는 경우에는 작은범위의 뒤집기를 먼저 실행한 후에 바깥쪽으로 나오는 과정을 거쳐야 한다고 생각했습니다.

2. 아이디어

문자열의 인덱스를 증가시키며, 작은 범위의 뒤집기를 먼저 실행하기 위해 네부분 각각 재귀함수를 실행하게 합니다. 왼쪽상단과 아래쪽상단, 오른쪽상단과 오른쪽하단을 바꾸어 뒤집히게 합니다.

3. 코드 설명

#include <iostream>

using namespace std;

char str[1005];		//문자열
int num;                  //문자열의 인덱스

string quadTree() {
	num++;           //한글자씩 증가시킨다.

	if (str[num] == 'w') {
		return "w";
	}
	else if (str[num] == 'b') {
		return "b";
	}

	string upl = quadTree();
	string upr = quadTree();
	string dol = quadTree();
	string dor = quadTree();

	return "x" + dol + dor + upl + upr;
}

int main() {      //테스트 케이스 수 입력
	int C;
	cin >> C;

	while (C--) {     //테스트 케이스만큼 반복
		string qt;      //쿼드트리 문자열 입력
		cin >> qt;

		num = 0;
		cout << quadTree() << endl;
	}

	return 0;
}

재귀함수를 사용해 반복해주었습니다. num을 이용해 문자열을 하나씩 증가시키면서 입력이 x일 경우(범위가 나눠질 경우) 작은 범위의 뒤집기를 위해 네부분 각각 재귀함수를 실행하게 하였습니다.

4. 막힌 점 및 개선 사항

런타임 오류가 발생합니다.