DFS(Depth-First-Search) 깊이 우선 탐색은 그래프의 모든 정점을 탐색하는 가장 단순한 방법이다.
현재 정점과 인접한 간선들을 하나씩 검사하다가 방문하지 않은 정점으로 향하는 간선이 있다면 해당 간선을 따라가 정점을 검사하고, 더 이상 갈 곳이 없는 막힌 정점에 도달하면 포기하고 마지막에 따라왔던 간선으로 되돌아간다.
거쳐왔던 모든 정점들에 대한 정보를 저장하기 위해서는 재귀호출을 이용해서 간단하게 해결할 수 있다. 재귀 호출한 함수가 종료하면 호출한 위치로 다시 돌아가기 때문이다.

무엇을 하든 기초가 정말 중요하다. 이전에 한 번 이 트리순회를 공부했을때에는 단순히 코드작성과 단순 이해만 했기 때문에 문제에 제대로 응용이 되지 않았던 것 같다.
그래서 이번에는 한 번 직접 손으로 스택 내부에 스택 프레임이 어떻게 쌓이는지 그려보며 내부의 재귀형태의 함수 호출은 어떻게 이루어지는지 살펴보았다. 또 스택과 함께 트리 구조도 어떻게 가지치기를 하는지 살펴보았다.

나중에 다시 복습을 위해 직접 그려 본 스택의 프레임과 트리구조를 아래에 첨부한다.