DFS(깊이 우선 탐색)

• 그래프 완전 탐색 기법
• 시작 노드에서 출발하여 탐색할 쪽 분기를 정한 뒤, 최대 깊이 탐색 후 다른쪽 분기 탐색
• 재귀함수, Stack 자료 구조 이용
• 시간복잡도(V + E)
• 재귀함수 구현시 스택 오버플로우를 유의
• 트리 완전 탐색에서 사용
• DFS 실행 횟수가 연결 요소 개수와 같음

핵심이론

• 노드 방문을 체크할 배열이 필요
• 그래프는 인접리스트로 표현

과정

• DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화
• 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입
• 스택 자료구조에 값이 없을 때 까지 반복
  • 방문한 노드는 확인후 스택에 넣지 않음