DFS란

한곳만 끝까지 파다가 아님 되돌아 오는 방식, Stack 자료구조를 사용

• 비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요

• 두가지 방법이 있음

  1. 깊이우선탐색(Depth First Search, DFS)(Stack사용)
  2. 넓이 우선 탐색(Breadth Frist Search, BFS)(Queue사용)

DFS 탐색 방법

1. 시작점(Root)에서 한 방향으로 갈 수 있는 경로가 있는 마지막까지 탐색함
2. 더이상 갈 곳이 없게 되면(Leaf Node만나면) 가장 마지막에 있었던 갈림길에서의 Node를 (Leaf Node입장에서의 Root node)로 돌아옴
3. 다른 방향의 Node로 탐색을 계속 반복하여 결국 모든 노드(정점)을 방문

Stack 자료구조를 이용해야 하는이유는 가장 마지막에 만났던 갈림길에서 다시 바로직전의 Node로 되돌아가서 방문하지 않은 다른 Node를 방문해야 하기 때문에 후입선출(LIFO)구조의 Stack 자료구조가 적절함

1. 경로를 역추적할 때 필요한 Stack 자료구조가 하나 필요하고, 방문 했는지 여부를 파악할 visit[] 배열이 필요하다