들어가기 전 사전 지식

스택 (Stack)

큐 (Queue)

재귀 함수 (Recursive Function)

그래프 (Graph)

DFS (Depth-First Search; 깊이 우선 탐색)

• 그래프의 깊은 곳으로의 탐색을 우선적으로 실행하는 탐색
• 스택 자료구조를 이용
• 시간 복잡도
  • 세타(V + E)
    • 재귀 호출 루프 수행에 걸리는 시간 세타(V)
    • 재귀 내 인접 정점 검사 시간 세타(E)
  • 재귀로 구현한 DFS는 컴퓨터 시스템 특성상 실제 수행 시간은 느려 질 수 있음

동작 과정

1. 탐색 시작 노드를 스택에 push하고 방문 처리.