지도에서 출발지와 목적지 사이의 경로 찾는 방법은 매우 다양합니다. 여기에서는 경로 탐색 알고리즘 중에서 동적 알고리즘 방식의 깊이우선탐색(DFS, Depth First Search) 알고리즘을 소개할게요.
깊이우선탐색 알고리즘은 출발지에서 다음 지점 중에 한 점으로 이동하고 해당 지점에서 다시 다음 지점으로 이동하는 것을 반복합니다. 만약 더 이상 이동할 곳이 없으면 이전 지점으로 다시 돌아와서 가지 않은 다른 지점으로 이동합니다. 이를 목적지에 도달할 때까지 반복하는 것입니다.
이와 같은 방법으로 문제를 해결하기 위해서는 이동하다가 막혔을 때 다시 돌아와서 다음 경로로 이동해야 하는데 이를 위해 경험 정보를 자료구조에 보관해야 합니다. 여기서 경험 정보란 지도에서 이동했었던 지점들의 목록입니다. 그리고 이동하다가 막혔을 때 가장 최근에 보관한 경험 정보를 얻어와서 진행해야 하므로 스택을 이용합니다.
앞에서 소개한 동적 알고리즘을 한 번 살펴보고 비교해 봅시다.
동적 알고리즘
초기 경험 정보를 생성
스택에 초기 경험 정보 Push
반복(스택이 빌 때까지)
스택에서 경험 정보를 Pop
꺼낸 온 경험에서 발생할 수 있는 다음 경험 정보 조사
반복(다음 경험 정보들을 순차적으로)
조건(결과에 도달하지 않았다면)
스택에 경험 정보를 Push
그렇지 않다면
결과에 보관
동적 알고리즘과 DFS 알고리즘을 비교하면 전체 흐름이 같습니다. 즉 DFS 알고리즘은 동적 알고리즘의 한 가지 종류입니다.
그런데 지도를 표현하려면 이제까지 다루었던 자료구조로 표현하는 것은 매우 어렵습니다. 따라서 여기에서는 DFS 알고리즘에 사용할 그래프를 정의한 후에 DFS 알고리즘을 설계 및 구현합시다.
그래프는 목적에 따라 다양한 형태로 구현할 수 있고 제공해야 할 함수도 다릅니다. 이 책에서는 그래프를 이용하는 알고리즘이 나올 때마다 목적에 맞는 그래프를 설계 및 구현하여 문제를 해결하기로 할게요.