algospot QUADTREE

문제 링크입니다: https://algospot.com/judge/problem/read/QUADTREE

책에 나와있는대로 분할을 이용하여 풀었습니다.

/*

쿼트리는 주어진 공간을 항상 4개로 분할해 재귀적으로 표현한다.

쿼드트리는 2^N * 2^N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축한다.

1. 이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b

2. 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w

3. 모든 픽셀이 같은 색이 아니라면 쿼드 트리는 이 그림을 가로 세로로 각각 2등분해 4개의 조각으로

   쪼갠 뒤 각각을 쿼드 트리 압축한다. 이 때 전체 그림의 압축 결과는

   x(왼쪽 위 부분의 압축 결과)(오른쪽 위 부분의 압축결과)(왼쪽 아래 부분의 압축결과)(오른쪽 아래 부분의 압축결과)

 

쿼드 트리로 압축된 흑백 그림이 주어졌을 때, 이 그림을 상하로 뒤집은 그림을

쿼드 트리 압축해서 출력하는 프로그램을 작성하시오

*/

#include <iostream>

#include <string>

using namespace std;

 

//쿼드 트리 뒤집기 문제를 해결하는 분할 정복 알고리즘

string reverse(string::iterator &it)

{

        char head = *it;

        ++it;

        //기저 사례: 1번 혹은 2번 과정일 경우

        if (head == 'b' || head == 'w')

               return string(1, head);

        //우선 각각의 칸을 뒤집는다(4분할된 칸들)

        string upperLeft = reverse(it); //4사분면

        string upperRight = reverse(it); //1사분면

        string lowerLeft = reverse(it); //2사분면

        string lowerRight = reverse(it); //3사분면

 

        //각각 위와 아래 조각들의 위치를 바꾼다(이래야 비로소 완전히 뒤집힌 것이다)

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

}

 

int main(void)

{

        int test_case;

        string picture;

        cin >> test_case;

        if (test_case < 0 || test_case>50)

               exit(-1);

       

        for (int i = 0; i < test_case; i++)

        {

               cin >> picture;

               if (picture.size() > 1000)

                       exit(-1);

 

               string::iterator it = picture.begin();

              

               cout << reverse(it) << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

참고: [프로그래밍 대회에서 배우는 알고리즘 문제해결전략]