[알고스팟] QUADTREE - 쿼드 트리 뒤집기 (C++)

문제

algospot.com/judge/problem/read/QUADTREE

algospot.com :: QUADTREE

 

풀이

 알고리즘 문제 해결 전략에 등자하는 대표적인 분할 정복 문제.

 

 해당 문제의 원본 그림의 크기는 최대 2의 20승 이기 때문에 단순히 원본 그림으로 복구시킨 후 다시 압축하는 것은 속도도 시간도 부족하다. 해당 문제는 문자열을 4개의 부분으로 분할하여 해결해야한다.

 

상하가 반전되므로 최소의 분할 대상 크기인 2x2에서는 (가)의 배열은 (나)로 변경되어야 한다.

(가)

(나)

이와 같은 순서 변경을 재귀 호출을 통해 진행하면 기저 사례에서 부터 차례로 변경되어 올라오므로 문제의 구현이 가능하다.

 

string Decompress(string ori)

 

기저사례는 ori의 가장 앞글자가 x가 아닌경우 해당 문자를 바로 반환한다.

 

 앞글자가 x라면 4개의 부분으로 나눠줘야하는데 이를 구현하기 위해 ori[1,ori.length() )를 순회하며 

ori[i]가 x가 나온다면 다시 4개의 추가 부분으로 분할되므로 count를 3 증가시켜 준다.

x가 아니라면 count를 -1 해준다.

최종적으로 count가 0이 된다면 해당 부분이 모두 탐색되어 각 부분 문자열을 저장하는 sub[subStrOrder]에 넣어준다.

 

 모든 부분이 탐색되었다면 UpToDownStr에 sub[2] -> sub[3] -> sub[0] -> sub[1] 순서로 재귀호출 하여 분할 정복한다.

 추가적으로 UpToDownStr의 맨앞에는 분할됨을 알리는 'x'를 삽입해주면 상하가 반전된 압축 문자열을 압축 해제없이 구현이 가능하다.

코드

위의 코드는 Decompress(string ori) 의 매개변수로 string ori 를 전달하여 복사 생성자가 계속되어 호출된다. 이는 메모리더 소모할 뿐만아니라 실행 속도까지 저하시키는데, 종만북에서는 string::iterator를  이용하여 훨씬 빠르고 간단한 코드를 구현하였다.

 

위의 Decompress를 종만북 스타일로 바꾸면 아래와 같다.

 

string Decompress(string::iterator &iter){ //참조 값 전달
  char head = *iter;
  ++iter; //'x'를 건너 뜀
  
  if(head != 'x')
    return string(1,head);
  string sub[4];
  sub[0] =Decompress(iter);
  sub[1] =Decompress(iter);
  sub[2] =Decompress(iter);
  sub[3] =Decompress(iter);
  return "x"+ sub[2]+ sub[3]+ sub[0]+ sub[1];
}