알고리즘 - DFS(Depth First Search)

그래프 탐색법 중 하나.

 

완전탐색이나 백트래킹등  탐색의 횟수, 그래프 경로가 정해져있거나 예측 가능한 경우의 문제에 사용.

 

1. 선택한 정점에서 해야할 작업 진행.

2. 선택한 정점에서 연결된 정점중 아직 방문하지 않은 정점 방문

3. 더 방문할 정점이 없으면(전부 방문 or 연결 정점 없음.) 이전 정점으로 되돌아감.

4. 1~3 반복.

 

이전 정점으로 되돌아가는 기능을 위해 Stack을 사용함. -> 재귀함수로도 가능함.