https://www.youtube.com/watch?v=lFtQnOhKnr0&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=21

📌 DFS (깊이 우선 탐색)

• 가장 많이 사용 됨
• 그래프 완전 탐색 기법 중 하나
  완전 탐색 : 그래프에 있는 모든 노드 탐색
• 그래프 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색
• 깊이 우선 탐색은 재귀 함수를 이용하므로 스택 오버플로우에 유의해야함
• 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등에 사용 가능
• 한번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요
• 후입선출(FILO) 특성을 가짐

특징	시간 복잡도 (노드 수 : V, 에지 수 : E)
재귀 함수로 구현	O(V+E)
스택 자료 구조 이용(후입선출(FILO) 특성)

*FILO : 먼저 들어온 DATA가 나중에 나간다

◾ 깊이 우선 탐색의 동작 과정

출처 : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=tjdowl123&logNo=220695561154

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

• 인접 리스트로 그래프 표현하기
  (0의경우 1,2로 갈 수 있기 때문에 시작점은 1 -> 인접 노드는 2,3
  1의경우 3,4로 갈 수 있기 때문에 시작점은 1 -> 인접 노드는 3,4 ...)

• 방문배열 초기화 하기
  boolean 등으로 취향에 맞게 세팅하기

• 시작 노드를 스택에 삽입하기
  스택에 시작 노드를 0으로 삽입 하는 경우,해당 위치의 방문 배열은 T,F,F,F... 가 된다.
  (아직 시작점 외에는 아무곳도 방문하지 않았기 때문에)
  

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

• pop을 수행하여 노드를 꺼낸 후 탐색 순서에 꺼낸 노드를 기록한다.

• 인접 리스트의 인접 노드를 스택에 삽입하여 방문 배열 체크
  (0 의 인접노드는 2,3이므로 스택에 2,3이 삽입)
  이 때 방문 배열은 T,T,T,F,F,... , 탐색 순서는 0 이 기록된다.

  
  

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

• 이미 다녀간 모드는 방문 배열을 바탕으로 재삽입 하지 않는 것이 핵심

→ 스택에 노드를 삽입 할 때 방문 배열을 체크
스택에서 노드를 뺄 때 탐색 순서에 기록,
인접 노드를 방문 배열과 대조하여 방문하지 않은 노드만 스택에 넣음