알고스팟_쿼드 트리 뒤집기 _분할정복

2020-04-22 · 배운 것 · 2분 읽기

https://algospot.com/judge/problem/read/QUADTREE

풀이방법

이 문제는 무식하게 풀면 쿼드트리의 압축풀기 -> 값 뒤집기 -> 다시 압축하기 이렇게 풀수도 있지만 너무 오래걸린다.

해결방법은 상하로 뒤집으면 밑의 그림처럼 된다는 것을 유의하고 압축을 풀지말고 string으로 주어진 문자열 상태에서 뒤집는 방법이다. 이러면 O(N)

조금더 자세하게 설명하자면 string을 조회하면서
1. 'b'나 'w'가 나오면 return 나온 문자
2. 'x'면 좌상(1), 우상(2), 좌하(3), 우하(4) 네가지 경우로 나누어 재귀를 돌린다.
3. return 'x' + 좌하(3) + 우하(4) + 좌상(1) + 좌우(2)

string getReverse(string::iterator& it)
{
	char head = *it;
	++it;
	if (head == 'b' || head == 'w')
		return string(1, head);
	string upperLeft = getReverse(it);
	string upperRight = getReverse(it);
	string lowerLeft = getReverse(it);
	string lowerRight = getReverse(it);

	return string("x") + lowerLeft + lowerRight + upperLeft + upperRight;
}

후기

나는 아직 멀었다. 맨날 모르네