이제 미로 탐색으로 돌아가 보자. 미로를 완전히 탐색하는 데 2가지가 필요하다. 방문했던 곳을 유지하는 방법과 아직 방문하지 않은 모든 방을 방문할 체계적인 방법이다. 방들은 어떤 식으로든 순서화되어 있고, 그래프에서 순서는 숫자로 표현한다고 가정하자. 그러면 모든 방을 방문하기 위해 첫 번째 방으로 가서 방문한 것으로 표시할 수 있다. 그다음 이 방에 연결된 방 중에서 첫 번째 방으로 가고 이러한 절차를 반복한다. 즉, 방문한 곳을 표시하고 연결된 방 중 아직 방문하지 않은 첫 번째 방으로 가는 것을 반복한다. 만일 연결된 방 중에서 방문하지 않은 방이 없다면 왔던 곳으로 되돌아가 그곳에서 아직 방문하지 않은 방이 남았는지를 확인한다. 방문하지 않은 방이 있으면 방문하지 않은 첫 번째 방을 방문하고 이후 같은 처리를 반복한다. 방문하지 않은 방이 없으면 되돌아가 다른 방을 탐색한다. 이것을 처음에 시작한 방으로 돌아올 때까지, 연결된 방들을 모두 방문했다는 것을 확인할 때까지 반복한다.

구체적으로 살펴보면 이해하기가 더 쉽다. 이 절차를 깊이 우선 탐색 또는 간단히 DFS(Depth-first Search)라고 하는데, 너비보다는 깊이로 들어가며 미로를 탐색하기 때문에 붙여진 이름이다. 그림 2-19의 미로 예시를 보면 그림 오른쪽에 인접 리스트가 있다. 노드는 리스트에 역순으로 삽입됨을 다시 한번 상기하자. 예를 들어, 인접 리스트에서 노드 0의 이웃하는 노드는 3, 2, 1 순으로 삽입되므로 리스트는 [0, 1, 2, 3]이 된다.

▲ 그림 2-19 깊이 우선으로 탐색할 미로