[탐색] DFS (깊이 우선 탐색)

✔ 깊이 우선 탐색

깊이 우선 탐색이란?

• 그래프 완전 탐색 기법 중 하나
• 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후
  다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘
• 재귀 함수 또는 스택 자료구조를 이용하여 구현이 가능 (FILO)
• V는 노드 수, E는 엣지 수일때, 시간 복잡도는 O(V + E)
• 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로에 유의
• 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상정렬에 응용

깊이 우선 탐색 과정

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
   • 인접 리스트로 그래프 표현하기
   • 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 방문 배열 초기화하기
   • 시작 노드 스택에 삽입하기
2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기
   • pop을 수행하여 노드 꺼내기
   • 꺼낸 노드를 탐색 순서에 기입하기
   • 꺼낸 노드의 인접 리스트의 인접 노드를 삽입하여 방문 배열 체크하기
3. 스택 자료구조에 값이 없을 때까지 반복하기
   • 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는 것이 핵심

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn