[Algorithm] 깊이 우선 탐색

in Algorithm

Elice Algorithm Code Challenge - Day 5 (깊이 우선 탐색)

목차

  1. DFS란?
  2. DFS특징
  3. DFS 시간 복잡도

깊이 우선 탐색 (DFS)

  • 특정 정점(노드)에서 시작해서 트리나 그래프에서 한 가지 경로를 최대한 깊게 탐색하고, 해당 경로를 끝까지 탐색한 후 다른 경로로 이동
  • 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가, 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사
  • 모든 정점을 방문하고자 하는 경우에 사용

DFS 특징

  • 일반적으로 재귀 함수 사용
    • Stack으로도 구현 가능
  • 모든 경우의 수에 대해 탐색을 진행
  • 사이클이 있는 경우, 무한 루프에 빠지지 않도록 방문 체크 해줘야함
  • BFS보다 깊은 경로를 빠르게 찾는데 용이
  • 진행 순서
    • Full-width image
  • 구현
    •   함수 DFS(now):
      현재 노드를 방문한 것으로 표시
      현재 노드를 출력

      모든 이웃노드 'next'에 대해서 반복:
          만약 'next'를 아직 방문하지 않았다면:
              DFS(next)

DFS 시간 복잡도

  • V : 정점(노드)의 수, E : 간선의 수
  • 인접 리스트로 표현된 그래프
    • O(V+E)
    • Full-width image
  • 인접 행렬로 표현된 그래프
    • O(V^2)
    • Full-width image
  • 희소 그래프
    • Sparse Graph
    • 그래프 내에 적은 숫자의 간선만을 가지는 그래프
    • 인접 행렬보다 인접 리스트 사용이 유리