[알고리즘 C언어] 6.2 깊이우선탐색(DFS) 알고리즘

지도에서 출발지와 목적지 사이의 경로 찾는 방법은 매우 다양합니다. 여기에서는 경로 탐색 알고리즘 중에서 동적 알고리즘 방식의 깊이우선탐색(DFS, Depth First Search) 알고리즘을 소개할게요.

 

깊이우선탐색 알고리즘은 출발지에서 다음 지점 중에 한 점으로 이동하고 해당 지점에서 다시 다음 지점으로 이동하는 것을 반복합니다. 만약 더 이상 이동할 곳이 없으면 이전 지점으로 다시 돌아와서 가지 않은 다른 지점으로 이동합니다. 이를 목적지에 도달할 때까지 반복하는 것입니다.

 

이와 같은 방법으로 문제를 해결하기 위해서는 이동하다가 막혔을 때 다시 돌아와서 다음 경로로 이동해야 하는데 이를 위해 경험 정보를 자료구조에 보관해야 합니다. 여기서 경험 정보란 지도에서 이동했었던 지점들의 목록입니다. 그리고 이동하다가 막혔을 때 가장 최근에 보관한 경험 정보를 얻어와서 진행해야 하므로 스택을 이용합니다.

 

앞에서 소개한 동적 알고리즘을 한 번 살펴보고 비교해 봅시다.

 

동적 알고리즘

    초기 경험 정보를 생성

    스택에 초기 경험 정보 Push

    반복(스택이 빌 때까지)

        스택에서 경험 정보를 Pop

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

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

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

                스택에 경험 정보를 Push

            그렇지 않다면

                결과에 보관

 

동적 알고리즘과 DFS 알고리즘을 비교하면 전체 흐름이 같습니다. 즉 DFS 알고리즘은 동적 알고리즘의 한 가지 종류입니다.

 

그런데 지도를 표현하려면 이제까지 다루었던 자료구조로 표현하는 것은 매우 어렵습니다. 따라서 여기에서는 DFS 알고리즘에 사용할 그래프를 정의한 후에 DFS 알고리즘을 설계 및 구현합시다.

 

그래프는 목적에 따라 다양한 형태로 구현할 수 있고 제공해야 할 함수도 다릅니다. 이 책에서는 그래프를 이용하는 알고리즘이 나올 때마다 목적에 맞는 그래프를 설계 및 구현하여 문제를 해결하기로 할게요.


학습에 도움이 되시면 ebook을 구입(판매가 3000원, ebook)하여 소장하시면 감사하겠습니다.

6.2.1 그래프 설계(DFS 알고리즘에 사용할 그래프)

6.2.2 그래프 구현(DFS 알고리즘에 사용할 그래프)

6.2.3 그래프 테스트(DFS 알고리즘에 사용할 그래프)

6.2.4 그래프 소스 코드

6.2.5 깊이우선탐색(DFS) 알고리즘의 경험(Heuristic)정보 설계

6.2.6 깊이우선탐색(DFS) 알고리즘의 경험 정보 구현

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

6.2.8 깊이우선탐색(DFS) 알고리즘 소스 코드