10.2.1 순열 문제 구현

10.2.1 순열 문제 구현

순열 문제.zip

순열 문제를 구현합시다.

0~9까지 공을 보관한 초기 경험 정보를 생성

스택에 보관

반복(스택이 비어 있지 않다면)

    스택에서 경험 정보 꺼내옮

    스택에서 꺼내온 경험 정보에서 다음 경험(공을 하나 더 꺼내는) 목록 조사

    반복(다음 경험 목록을 순차적으로 반복)

        바구니에 공이 비면

            결과 출력

        그렇지 않다면

            스택에 보관

 

먼저 공을 보관한 바구니를 공의 번호를 보관하는 벡터로 표현할게요.

typedef vector<int> Bucket;

typedef Bucket::iterator BIter;

typedef Bucket::const_iterator CBIter;

그리고 경험 정보를 벡터에 보관한 형식을 Heues로 정의할게요.

class Heuristic;

typedef vector<Heuristic *> Heues;

typedef Heues::iterator HIter;

typedef Heues::const_iterator CHIter;

 

경험 정보를 Heuristic 클래스로 정의합시다.

class Heuristic

{

원래 공이 있는 바구니와 꺼낸 공이 있는 바구니가 필요하겠죠.

    Bucket original;

    Bucket out;

public:

생성자에는 공이 있는 바구니를 입력 인자로 받습니다.

    Heuristic(Bucket bucket);

현재 경험에서 다음 경험 목록을 열거하는 메서드를 제공해야겠죠.

    Heues EnumNext();

결과를 출력하는 메서드를 제공합시다.

    void View()const;

원래 공이 있는 바구니가 빈 상태인지 판단하는 메서드를 제공합시다.

    bool IsEmpty()const;

private:

내부에서 이전 경험 정보에서 하나의 공을 꺼내는 경험을 생성하는 생성자가 필요합니다.

    Heuristic(const Heuristic *bheu,int ball);

};

 

생성자를 구현합시다.

Heuristic::Heuristic(Bucket bucket)

{

입력 인자로 들어온 바구니를 original에 대입하세요.

    original = bucket;

}

 

다음 경험 정보 목록을 조사하는 메서드를 구현합시다.

Heues Heuristic::EnumNext()

{

    Heues heues;

현재 경험에서 다음 경험은 original에 있는 공을 하나 꺼내어 out에 집어 넣는 것입니다. 이를 위해 original에 있는 공을 순차적으로 방문하여 공을 하나 꺼내어 out에 집어 넣는 다음 경험을 생성해야 합니다.

    BIter seek = original.begin();

    BIter last = original.end();

    for(  ;seek != last ; ++seek)

    {

현재 반복자의 공을 꺼낸 경험 정보를 생성하여 컬렉션에 보관합니다.

        //하나의 공을 꺼낸 경험 정보를 생성하여 보관

        heues.push_back(new Heuristic(this,*seek));

    }

    return heues;

}

 

경험 정보를 출력하는 메서드에서는 꺼낸 공을 순서대로 출력합니다.

void Heuristic::View()const

{

    CBIter seek = out.begin();

    CBIter last = out.end();

    for(  ;seek != last ; ++seek)

    {

        cout<<(*seek)<<" ";

    }

구분하기 위해 개행을 출력하세요.

    cout<<endl;

}

 

비었는지 판별하는 메서드에서는 original이 비었는지 판별한 값을 반환하세요.

bool Heuristic::IsEmpty()const

{

    return original.empty(); //바구니가 비었는지 판별

}

 

이전 경험에서 하나의 공을 꺼내는 생성자를 구현합시다.

Heuristic::Heuristic(const Heuristic *bheu,int ball)

{

먼저 바구니를 복사하세요.

    out = bheu->out;

    original = bheu->original;

 

공이 있는 바구니를 순차적으로 방문해야 합니다.

    BIter seek = original.begin();

    BIter last = original.end();

    for(  ;seek != last; ++seek)

    {

만약 반복자의 위치의 공과 입력 인자 ball이 같으면 original에서 꺼내어 out에 보관합니다.

        if((*seek)==ball) //seek위치의 공과 ball이 같으면

        {

            original.erase(seek);//공을 꺼냄

            out.push_back(ball);//꺼낸 바구니에 보관           

            break;

        }       

    }

}

 

이제 동적 프로그래밍으로 순열 문제를 표현합시다. 여기에서는 진입점 main에 표현할게요.

int main()

{

경험 정보를 보관하는 스택이 필요합니다.

    stack<Heuristic *> hs;

 

초기 경험 정보를 만들기 위해 0부터 9까지 바구니에 보관합시다.

    Bucket bucket;

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

    {

        bucket.push_back(i);

    }

 

초기 경험 정보를 생성하여 스택에 보관하세요.

    Heuristic *heu = new Heuristic(bucket);//hs.push(0~9까지 공을 보관한 초기 경험 정보를 생성

    hs.push(heu);//스택에 보관

 

스택이 빌 때까지 알고리즘은 반복합니다.

    while(hs.empty() == false) //반복(스택이 비어 있지 않다면)

    {

 

스택에서 경험 정보를 꺼냅니다.

        heu = hs.top();//스택에서 경험 정보 꺼내옮

        hs.pop();

 

스택에서 꺼내온 경험 정보에서 공을 하나 꺼내는 다음 경험 목록을 조사합니다.

        Heues nheues = heu->EnumNext();//스택에서 꺼내온 경험 정보에서 다음 경험 목록 조사

 

조사한 경험 목록을 순차적으로 반복합니다.

        HIter seek = nheues.begin();

        HIter last = nheues.end();

        for(  ;seek != last; ++seek)//반복(다음 경험 목록을 순차적으로 반복)

        {

만약 바구니에 공이 비었으면 결과를 출력합니다.

            if((*seek)->IsEmpty())//바구니에 공이 비면

            {

                (*seek)->View();//결과 출력

출력한 경험 정보는 다시 사용하지 않으므로 소멸하세요.

                delete (*seek);

            }

            else//그렇지 않다면

            {

그렇지 않다면 스택에 보관합니다.

                hs.push(*seek);//스택에 보관

            }

        }

더 이상 필요없는 경험 정보를 소멸하세요.

        delete heu;

    }

    return 0;

}

 

▷ 실행 결과

9 8 7 6 5 4 3 2 1 0

9 8 7 6 5 4 3 2 0 1

9 8 7 6 5 4 3 1 2 0

9 8 7 6 5 4 3 1 0 2

9 8 7 6 5 4 3 0 2 1

9 8 7 6 5 4 3 0 1 2

9 8 7 6 5 4 2 3 1 0

9 8 7 6 5 4 2 3 0 1

9 8 7 6 5 4 2 1 3 0