04. QUADTREE

알고리즘문제해결전략 p189

문제

쿼드 트리 뒤집기 (문제ID:QUADTREE, 난이도 하)

알고스팟 링크

풀이

분할 정복 카테고리에 있지만

문제의 내용 자체가 분할 정복의 원리를 사용한 것일 뿐이고

실제로 풀이는 그냥 stack을 사용해서 하면 된다. (DFS)

풀이의 아이디어는 상하를 뒤집는 방법에 있어서,

x마다 하위의 노드들을 전부 앞뒤로 바꿔주면 전체적으로 상하로 뒤집은 결과가 된다는 것.

책의 그림 7.6과 그 밑에 개념적인 설명이 잘 되어있으니 잘 읽어보자

그걸 구현 하는 방법은 stack을 통해서 뒤집을게 모이면 계속 뒤집어 주면 된다.

단지 살짝 주의해야 하는 점은 뒤집은 직후에 그 뒤집었던 x를 루트로 하는 부분트리가

상위 x의 4번째 node였을 때 곧바로 한번 더 뒤집어야 한다는 점이다.

나는 그 부분은 while문을 통해서 구현했다. 

코드