[Algorithm] DFS - 깊이 우선 탐색

1. 그래프 탐색이란,

   • 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 → 특정 도시에서 다른 도시로 갈 수 있는지 없는지 → 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지
     

2. 깊이 우선 탐색이란,

   • 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

   • 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.

   • 넓게 탐색하기 전에 깊게 탐색하는 것

   • 사용하는 경우 : 모든 노드를 방문하고자 할 때 선택

   • 깊이 우선 탐색 VS 너비 우선 탐색

     	깊이 우선 탐색	너비 우선 탐색
     복잡도	小	大
     단순 검색 속도	大	小

3. 깊이 우선 탐색의 특징

   • 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
   • 전위 순회를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
   • 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. → 이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다.
     

4. 깊이 우선 탐색의 과정

   

5. 깊이 우선 탐색의 구현방법

   • 순환 호출 이용
   • 명시적 스택 사용 : 명시적인 스택을 사용하여 방문한 정점들을 저장하였다가 다시 꺼내어 작업한다.

6. 깊이 우선 탐색의 시간복잡도

   • DFS는 그래프(정점의 수 : N, 간선의 수 : E)의 모든 간선을 조회한다.
     • 인접 리스트로 표현된 그래프의 시간복잡도 = $O(N+E)$
     • 인접 행렬로 표현된 그래프의 시간복잡도 = $O(N^2)$
   • 그래프 내의 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph)의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.

➰ References

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html