[Algorithm] 깊이 우선 탐색 목차 1. DFS란? 2. 그래프란? 그래프의 특징 그래프의 종류 그래프 용어 1. DFS란? 깊이 우선 탐색(Depth-First-search)은 그래프 완전 탐색 기법중 하나 그래프의 시작 노드에서 출발하여 탐색할 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 분기 쪽으로 이동하여 탐색을 수행하는 알고리즘 트리의 완전 탐색에 사용된다. 깊이 우선탐색 특징 기능 특징 시간 복잡도 (노드 -V, 엣지 - E) 그래프 완전 탐색 - 재귀 함수로 구현 - 스택 자료구조 이용 O(V+E) DFS는 사실상 재귀함수문제와 다름없다. 재귀 함수를 이용하므로 스택오버플로에 유의해야 한다. DFS를 이용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상..