깊이 우선 탐색 (DFS, Depth-First Search)

깊이 우선 탐색

---

깊이 우선 탐색

• DFS (Depth-First Search)
• 깊이 우선 탐색 시 끝없이 깊어지는 것을 방지하기 위해 깊이 제한 적용 (조건을 이용)
• 목표 노드에 도달하지 못하면 부모노드로 되돌아감 (부모노드로 되돌아가는 것을 백트래킹(backtracking)이라고 함)
• 하나의 정점에서 아래쪽으로 깊게 탐색 후 더이상 탐색이 불가능하면 되돌아가 인접한 다른 노드를 탐색
  

  

• 시간 복잡도 : O(V + E)
  V : 정점의 개수 (위 사진에서 A, B, C, D, E, F, G)
  E : 간선의 개수 (각 정점을 잇는 선)
• 공간 복잡도 : O(V)
  방문 여부를 확인하기 위한 visited 배열 추가 필요
  
  
• 방문 여부를 확인하기 위한 visited 배열 필요성
  방문 여부를 체크하지 않으면 두 번 탐색할 수 있음. (ex. D에서 부모노드로 돌아갔을 때 또 비교할 수 있음)
  싸이클(무한루프) 방지를 위해 필요
  
  
• 재귀 및 스택으로 구현 가능
• 장점
  1) 지나온 노드들의 경로만 알고 있으면 되기 때문에 공간을 비교적 적게 차지함
  2) 목표노드가 깊을수록 빨리 해를 구할 수 있음
  
  
• 단점
  1) 해가 없는 경로에 빠질 수 있음 (특정 깊이까지만 탐색하고 발견하지 못하면 다시 돌아가 다른 경로로 이동하는 방법으로 해결가능)
  2) 최단경로가 된다는 보장이 없음 (검색 노드가 발견되면 탐색을 종료하기 때문)
  
  
• 사용예제 (작성 예정)
  1) 미로에서 출구를 찾기 위한 경로 탐색