[Week 1] QUADTREE self review - Choi-mina

[Choi-mina]

QUADTREE self review

• 파일명: PQR/QUADTREE/Choi-mina.cpp
• 수행시간: 8ms

1. 고민 과정

재귀함수를 이용해야해서 결과를 위해 어떻게 재귀함수를 짜야할지 고민을 많이 했습니다.

2. 풀이 아이디어

분할정복 문제입니다.
스터디 자료에 있는 재귀함수 템플릿을 이용해 구현했습니다.

3. 작성한 코드와 설명

int c, position;
string picture;

string quad() {
	char head = picture[position++];

	if (head == 'w' || head == 'b') {
		return string(1, head);
	}
	else {
		string leftUpper = quad();
		string rightUpper = quad();
		string leftLower = quad();
		string rightLower = quad();
		return 'x' + leftLower + rightLower + leftUpper + rightUpper;
	}
}

quad()함수는 문자열을 뒤집어서 반환하는 함수입니다.
position변수는 위치를 가리키는 변수로 선언해주었습니다.
head라는 변수에 위치의 문자를 넣어주고 조건문을 통해 w, b, x를 확인하게 했습니다.
쿼드 트리를 뒤집는 것이기 때문에 leftLower + rightLower + leftUpper + rightUpper로 리턴해주었습니다.

int main() {
	cin >> c;
	for (int i = 0; i < c; i++) {
		cin >> picture;
		cout << quad() << endl;
		position = 0;
	}
	return 0;
}

main에서 입출력 하는 코드를 적어주었습니다.