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

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

---

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

 

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

 

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

 

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

 

동적 알고리즘

    초기 경험 정보를 생성

    스택에 초기 경험 정보 Push

    반복(스택이 빌 때까지)

        스택에서 경험 정보를 Pop

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

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

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

                스택에 경험 정보를 Push

            그렇지 않다면

                결과에 보관

 

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

 

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

 

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

---

[C언어 알고리즘] 6.2.1 그래프 설계(DFS 알고리즘에 사용할 그래프)

[C언어 알고리즘] 6.2.2 그래프 구현(DFS 알고리즘에 사용할 그래프)

[C언어 알고리즘] 6.2.3 그래프 테스트(DFS 알고리즘에 사용할 그래프)

[C언어 알고리즘] 6.2.4 그래프 테스트 소스 코드

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

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

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

[C언어 알고리즘] 6.2.8 깊이우선탐색(DFS) 알고리즘 소스 코드