[알고리즘] 깊이 우선 탐색(DFS, Depth, First Search) - 컴도리돌이

깊이 우선 탐색

---

• 너비 우선 탐색이 시작 정점에서 시작하여 점차 탐색 범위를 넓혀 나가는 방식이라면, 깊이 우선 탐색(DFS, depth, first search)은 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식이다.
• 방문할 정점이 없어지면 다른 경로를 찾아 다시 멀어지는 방향으로 탐색을 반복한다.
• 이러한 그래프 탐색 방법을 백트래킹(backtracking)이라고 한다.
• 시간 복잡도 : O(V+E) 
• DFS는 대체로 시작 정점에서 멀이 있는 정점을 찾을 때 적합하다.
• DFS는 최단 경로를 보장하지 않는다.
• DFS에 의해 생성된 검색 트리는 길고 좁은 편이며, 상대적으로 적은 메모리를 필요로 한다.

출처 : https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

 

깊이 우선 탐색 관련 문제

---

[프로그래머스]

[level2] 타겟 넘버  :  https://comdolidol-i.tistory.com/193

[level3] 단어 변환 : https://comdolidol-i.tistory.com/195

[level3] 여행 경로 : https://comdolidol-i.tistory.com/196