[Week 1] QUADTREE self review - Queue-ri

[Queue-ri]

QUADTREE self review

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

1. 고민 과정

쿼드 트리 원본 크기가 너무 크므로 압축된 문자열만 가지고 정답을 도출해야 했습니다.

또한 문제에서 재귀를 직접적으로 언급하고 있으므로 재귀함수를 사용하여 풀이법을 구현했습니다.

2. 풀이 아이디어

분할 정복 문제입니다.

1주차 세션에서 다루었던 재귀함수 템플릿 내용대로 구현했습니다.

인덱스는 iterator 말고 그냥 C 스타일로 해봤는데 string 변환 오버헤드 때문에 그다지 메리트 있는 것 같진 않습니다.

3. 작성한 코드와 설명

Advanced-Algorithm-Study/PQR/QUADTREE/Queue-ri.cpp

Lines 9 to 20 in 16801e8

	string upside_down(string &cq) {
	char cell = cq[idx++];
	if (cell == 'b' || cell == 'w') return string(1, cell);
	string s1, s2, s3, s4;
	s1 = upside_down(cq);
	s2 = upside_down(cq);
	s3 = upside_down(cq);
	s4 = upside_down(cq);
	return "x" + s3 + s4 + s1 + s2;
	}

쿼드 트리 문자열을 뒤집어서 반환해주는 재귀함수입니다.

idx 변수는 전역으로 놓고 각 함수 내에서 조작하여 다음 재귀 호출 시 어느 위치에서 파싱할 지 결정해줍니다.

재귀 종료 조건은 해당 위치에 b 또는 w가 있는 경우이며, 쿼드 트리는 분할 시 4등분되기 때문에 x의 경우 재귀를 4번 호출해줍니다.

Advanced-Algorithm-Study/PQR/QUADTREE/Queue-ri.cpp

Lines 22 to 31 in 16801e8

	int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int TC; cin >> TC;
	while (TC--) {
	string comp_quad; cin >> comp_quad;
	cout << upside_down(comp_quad) << endl;
	idx = 0;
	}
	}

main에선 간단한 입출력 최적화와 다음 test case를 위한 변수 세팅을 해줍니다.