깊이 우선 탐색, DFS 이란? DFS 란 트리에서 생각해보면 트리를 탐색할 때 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 매우 유사합니다. 즉 DFS는 특정 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법입니다. DFS 는 스택을 사용해 구현합니다. 아래의 동작과 구현에서 확인하겠지만, 깊이 우선 탐색을 통해 그래프를 탐색하게 되면 모든 간선을 조사하므로 정점의 수가 n 이고 간선의 수가 e인 그래프인 경우, 그래프가 인접 행렬로 표시되어 있다면 O(n^2), 인접 리스트로 표현되어 있는 경우는 O(n+e) 가 됩니다. 따라서 희소 그래프인 경우는 DFS는 인접 리스트의 사..
