[분할 정복] QUADTREE

#include <iostream>
#include <string>
//all black -> b
//all white -> w
//all different - > quad : x(left up)(right up)(left down)(right down)
//Upside down
void dividePicture(const std::string& picture, std::string (&pieces)[4], int index, int currentPiece, int count)
{
    if(index < picture.length())
    {
        pieces[currentPiece] += picture.at(index);
 
        if(count == 0 && picture.at(index) != 'x')
            return dividePicture(picture, pieces, index + 1, currentPiece + 1, count);
        else if(picture.at(index) != 'x') 
            return dividePicture(picture, pieces, index + 1, currentPiece, count - 1);
        else if(picture.at(index) == 'x')
            return dividePicture(picture, pieces, index + 1, currentPiece, count + 3);
    }
    return;
}
std::string upsideDown(std::string picture)
{
    std::string pieces[4] = {"", "", "", ""}, upsideDownPicture = "";
 
    if(picture.at(0) == 'x')
    {
        dividePicture(picture, pieces, 1, 0, 0);
 
        upsideDownPicture = "x" + upsideDown(pieces[2]) + upsideDown(pieces[3])
                                + upsideDown(pieces[0]) + upsideDown(pieces[1]);
        
        return upsideDownPicture;
    }
    else
        return picture;
 
}
int main(void)
{
    int testCase = 0;
    std::string picture = "";
    
    std::cin>>testCase;
 
    for(int i = 0; i < testCase; i++)
    {
        std::cin>>picture;
        std::cout<<upsideDown(picture)<<std::endl;
    }
}

 

1. 문제를 더 작은 문제로 분할

    그림을 4등분하여 각각의 그림에 대해 재귀호출한다. (n)

 

2. 각 문제에 대해 구한답을 원래 문제에 대한 답으로 병합

    각 부분문제는 + 연산자에 의해 병합되어진다. (n)

 

3. 시간 복잡도 계산

    upsideDown함수가 n번 실행되면 각각 단계마다

    dividePicture가 n*log(4)n번 실행되므로

    O(n)  + O(nlgn)만큼의 시간이 걸린다.

 

4. 더 빠른 시간안에 수행할 수 있는지?

    dividePicure 함수에서 각각 문자열을 하나씩 대조하지 않고

    upsideDown 함수에서 각각 문자열을 하나씩 대조하여

   

    'x'가 나오면 좌->우 상->하 순서대로 분할하면서 문자 대조,

    'b', 'w'가 나오면 리턴 하도록 구현하면

   

    결국 n 번의 수행만에 답을 구할 수 있게 된다.

 

 

쿼드트리