깊이 우선 탐색(DFS, Depth First Search)

그래프 완전 탐색 기법 중 하나
그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘
특징

• 재귀 함수로 구현
• 스택(FILO) 자료구조 이용

깊이 우선 탐색은 재귀 함수를 이용하므로 스택 오버플로 유의
한 번 방문한 노드를 다시 방문하면 안 됨 -> 노드 방문 여부를 체크할 배열 필요
그래프는 인접 리스트로 표현

핵심 이론

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
   DFS를 위해 필요한 초기 작업 : 인접 리스트로 그래프 표현하기, 방문 배열 초기화하기, 시작 노드 스택에 삽입하기
   

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽잉ㅂ하기
   pop을 수행하여 노드를 꺼내기.
   꺼낸 노드를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽입하며 방문 배열을 체크
   

3. 스택 자료구조에 값이 없을 때까지 반복하기
   앞선 과정을 스택 자료구조에 값이 없을 때까지 반복
   이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는 것이 핵심
   
   이어서 설명하면 스택에서 3을 꺼내며 탐색 순서에 기록하고 인접 노드 4를 스택에 삽입하며 방문 배열에 체크
   4를 꺼내며 탐색 순서에 기록하고 6을 삽입하며 방문 배열에 체크
   6을 꺼내며 탐색 순서에 기록하고 6과 인접한 노드는 없으므로 추가 삽입 X
   계속해서 스택에서 2를 꺼내며 탐색 순서에 기록하고 2와 인접한 5, 6을 삽입하기 위해 봄. 이때 6은 방문 배열에 T로 체크되어 있으므로 5만 삽입
   이 과정을 스택이 빌 때까지 진행