DFS란? DFS(depth first search): 한 방향으로만 깊이 들어가다가 더 이상 갈 곳이 없으면 돌아가서 다른 방향으로 탐색하는 방법이다. 너비 우선 탐색에 비해 구현이 간단하지만 단순 검색 속도 자체는 BFS에 비해서 느리다는 특징이 있다. 말로만 해서는 이해가 쉽지 않은데 예시를 통해서 보도록 하자. 탐색을 $0$번 정점에서 시작할 것이다. 방문한 정점은 색을 주황색으로 표시하고 현재 위치를 화살표로 나타낼 것이다. dfs의 목적은 그래프를 탐색하는 것이므로 한 번 방문한 정점은 다시 방문하지 않는다. $0$번 정점에서 시작해서 $1$번 정점으로 가고 $1$번 정점에서 $3$번 정점으로 가고 $3$번 정점에서 $6$번 정점으로 간다. $6$번 정점에서 더 이상 갈 곳이 없으므로 바로 전..