DFS

DFS ?

• 그래프 완전 탐색이 필요할 때, 즉 모든 노드를 방문해야 할 때 DFS를 주로 사용한다.
• 말 그대로 그래프의 시작 노드에서 탐색할 분기를 하나 정하게 되면 그 분기의 최대 깊이까지 탐색을 마친 후 다른 분기로 이동하여 다시 최대 깊이까지 탐색을 수행하는 알고리즘이다.
• 미로 탐색과 같은 백트래킹 문제, 모든 경로를 탐색해야 하는 문제나 그래프가 좁고 깊은 구조일 때 적합하다 !
• 단, 최단 경로를 항상 보장하진 않기 때문에, 최단 거리 탐색 문제엔 적합하지 않다 !
• Stack과 재귀함수를 이용하여 구현한다.

💡 DFS 핵심 개념 - 방문 여부 체크

• DFS는 한 번 방문한 노드를 재방문하면 안되기 때문에, 각각의 노드에 대한 방문 여부를 체크할 수 있는 배열이 필요하다 !

💡 DFS 핵심 개념 - 그래프 구현 방법에 따라 달라지는 시간 복잡도

노드의 수 = V, 간선의 수 = E

1. 인접 리스트를 이용한 방법 - O(V + E)