정의

깊이 우선 탐색(DFS)은 그래프에서 시작 노드로부터 한 방향으로 가능한 깊이 탐색하고, 더 이상 갈 곳이 없으면 되돌아와 다른 방향을 탐색하는 알고리즘입니다.

핵심 특성

• ✓스택(Stack) 사용 - 후입선출 (LIFO)
• ✓한 경로를 끝까지 탐색 후 백트래킹
• ✓BFS와 달리 스택에서 꺼낼 때 방문 표시
• ✓재귀로도 구현 가능 (호출 스택 활용)

시간 복잡도