10.2.1 순열 문제 구현

순열 문제를 구현합시다.

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

스택에 보관

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

    스택에서 경험 정보 꺼내옮

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

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

        바구니에 공이 비면

            결과 출력

        그렇지 않다면

            스택에 보관

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

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

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

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

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

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

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

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

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

생성자를 구현합시다.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

▷ 실행 결과