1. 깊이 우선 탐색

• 깊이 우선 탐색(DFS: depth-first-search)은 그래프 완전 탐색 기법 중 하나이다.
• 깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.
• 깊이 우선 탐색 과정
  • 깊이 우선 탐색은 먼저 시작 정점에서부터 임의의 인접한 정점으로 깊이 탐색을 진행한다.
  • 이떄 방문한 정점은 반드시 방문되었다는 표시를 해야 하고, 탐색은 아직 방문하지 않은 인접 정점으로만 가능하다.
  • 만약 현재 정점에서 더이상 방문하지 않은 인접 정점을 찾아 다시 동일한 방법의 탐색을 진행한다.

• 깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로에 유의해야 한다.

✅ 깊이 우선 탐색의 핵심 이론

• DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하며, 그래프는 인접 리스트로 표현한다.

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
   1. DFS를 위해 필요한 초기 작업
      1. 인접 리스트로 그래프 표현하기
      2. 방문 배열 초기화 하기 (스택에 시작 노드를 1로 삽입할 때 해당 위치의 방문 배열을 체크한다.)
      3. 시작 노드 스택에 삽입하기

1. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기
   1. pop을 수행하여 노드를 꺼낸다.
   2. 꺼낸 노드를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽입하며 방문 배열을 체크한다.
   3. 방문 배열: T, T, T, F, F, F

1. 스택 자료구조에 값이 없을 때까지 반복하기
   1. 앞선 과정을 스택 자료구조에 값이 없을 때까지 반복한다.
   2. 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는다.

• 스택에서 3을 꺼내며 탐색 순서에 기록하고 인접 노드 4를 스택에 삽입하며 방문 배열에 체크
• 4를 꺼내며 탐색 순서에 기록하고 6을 삽입하며 방문 배열에 체크한다.
• 6을 꺼내며 탐색 순서에 기록하고 6과 인접한 노드는 없으므로 추가 삽입은 없다.