CH14-3그래프의 탐색(4)
이번시간에는 깊이 우선탐색의 구현을 위한 모델을 살펴보자…
깊이우선탐색의 구현에서 고민해야 할 부분은… 자기에게 연결된 정점중 한 정점을 골라 탐색하는게 아니라
더이상 자신이 탐색할 수 있는 정점이 주변에 없을때 자기 이전의 노드로 돌아가는 과정을 구현하는 것이고, 이는 스택으로 구현된다.
스택에 정점에 대한 정보를 언제 push하는가?
연락을 취할 기회를 다음 정점에게 전달하고 나면, 그때 스택에 정보가 올라간다.
즉 동수가 지민에게 연락을 취한 후에, 동수의 정보가 스택에 올라간다.
여기까지 왔다고 해보자. 수정이 다음 노드를 탐색하는 차례이다… 그런데 수정은 더이상 연락을 취할 정점이 없다. 그럴때 스택을 참조한다! 스택에서 push하면 자기에게 연락준 정점의 주소를 얻을 수 있다.
정희도 연락할 정점이 없으니 스택에서 다시 push한다. 민석으로 주소가 옮겨가면, 그때 다시 자신과 연결된 노드에서 탐색할 노드를 찾는다.
지율이라는 정점이 있다. 지율로 옮겨가고나면, 민석은 다시 스택에 쌓인다..
그렇게 해서 초기로 돌아온다는건.. 결국 스택에서 모든 정점이 push되는걸 의미하게 된다.
즉 동수가 push되고 나서, 동수에게 마지막으로 탐색기회를 부여하고 나면, DFS는 자신이 종료될 타이밍이라는걸 판단한다.
다음시간에는 실제 코드레벨에서 구현해보자.