DongDD's IT

DFS(Depth-First-Search) Algorithm DFS Algorithm- 그래프나 트리같은 자료구조에서 탐색을 할 때 사용하는 알고리즘 중 하나- DFS는 구현 방식이 여러가지 있고 각각으 시간 복잡도는 다름- 하나의 정점부터 가장 깊이가 깊은 곳까지 탐색하며 방문하지 않은 모든 정점들을 탐색함 DFS Complexity- 인접 리스트를 사용해 그래프를 구현하는 경우와 인접 행렬을 이용해 구현하는 경우 시간복잡도가 다름 1) 인접 리스트- 한 정점에서 방문할 수 있는 정점을 간선 기준으로 탐색할 수 있기 때문에 O(V+E)의 시간 복잡도를 갖는다. 2) 인접 행렬- 방문할 정점을 찾을 때 연결된 모든 정점을 순회하며 이어져 있는지 체크를 해야 되기 때문에 O(V^2)의 시간 복잡도를 갖는다..