TIL_221128

DFS

DFS는 Depth First Search 라고 했습니다!
갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

• 노드를 방문하고 깊이 우선으로 인접한 노드를 방문
• 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문
• 만약 끝에 도달했다면 리턴

---

깊이 우선 탐색(DFS) 과정

1. a 노드(시작 노드)를 방문한다.
   • 방문한 노드는 방문했다고 표시한다.
2. a와 인접한 노드들을 차례로 순회한다.
   • a와 인접한 노드가 없다면 종료한다.
3. a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 한다.
   • b를 시작 정점으로 DFS를 다시 시작하여 b의 이웃 노드들을 방문한다.
4. b의 분기를 전부 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안 된 정점을 찾는다.
   • 즉, b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있다는 뜻이다.
   • 아직 방문이 안 된 정점이 없으면 종료한다.
   • 있으면 다시 그 정점을 시작 정점으로 DFS를 시작한다.

참고자료: https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html