7.2.7 깊이우선탐색(DFS) 알고리즘 테스트 코드 작성

앞에서 깊이 우선 탐색(DFS) 알고리즘에 사용할 그래프와 Heuristic 을 구현하였습니다.  이번에는 깊이 우선 탐색(DFS) 알고리즘에 사용할 그래프를 생성하여 구성하는 함수를 작성합시다.

깊이우선탐색(DFS) 알고리즘 테스트 코드 작성 전에 다시 한 번 동적 알고리즘의 의사코드를 확인합시다.

 

동적 알고리즘

    초기 경험 정보를 생성

    스택에 초기 경험 정보 Push

    반복(스택이 빌 때까지)

        스택에서 경험 정보를 Pop

        꺼낸 온 경험에서 발생할 수 있는 다음 경험 정보 조사

        반복(다음 경험 정보들을 순차적으로)

            조건(결과에 도달하지 않았다면)

                스택에 경험 정보를 Push

            그렇지 않다면

                결과에 보관

알고리즘 테스트에 사용할 그래프를 생성합니다.

스택을 생성합니다.

초기 경험 정보를 생성합니다. 여기에서는 A점을 출발점으로 하고 H점을 도착점으로 할게요.

초기 경험 정보를 스택에 보관합니다.

스택에 경험 정보가 남아있다면 반복 수행합니다.

스택에 보관한 경험 정보를 꺼내옵니다.

다음 경험 정보 목록을 보관할 동작 배열을 생성합니다.

현재 경험 정보에서 수행할 수 있는 다음 경험 정보 목록을 구합니다.

조사한 다음 경험 정보 목록의 시작과 끝을 구합니다.

순차적으로 이동하면서 다음 경험 정보를 구합니다.

만약 도착점에 도달하면 경험 정보를 출력하고 소멸합시다.

도착점에 도달하지 않았다면 스택에 보관합니다.

임시로 다음 경험 정보 목록을 보관했던 배열을 소멸합니다.

 

다음은 실행 결과입니다.