[Do it! 알고리즘 코딩테스트 with Python] 깊이 우선 탐색 (DFS)

깊이 우선 탐색(DFS)

최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하는 것

기능	특징	시간 복잡도(노드 수: V, 에지 수: E)
그래프 완전 탐색	- 재귀 함수로 구현 - 스택 자료 구조(FIFO)	O(V + E)

 

깊이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단결선 찾기, 사이클 찾기, 위상 정렬

 

- 노드 방문 여부를 체크할 배열이 필요!!
- 인접 리스트

 

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기

2. 스택에서 노드를 꺼낸 후, 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기

3, 스택 자료구조에 값이 없을 때까지 반복하기