DFS란?
•
그래프 완전 탐색 기법 중 하나
•
그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행
•
재귀 함수 or 스택 자료구조 이용
◦
재귀 함수를이용하므로 스택 오버플로(stack overflow)에 유의해야 함
•
시간 복잡도 O(V + E) - 노드 수(V), 에지 수(E)
•
한 번 방문한 노드를 다시 방문하면 안 됨
◦
노드 방문 여부를 체크할 배열이 필요
◦
그래프 - 인접 리스트로 표현
◦
DFS의 탐색 방식 - LIFO(후입선출), 스택을 이용
•
단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등으로 활용