dfs

2. DFS(Depth-Find-Search) : 깊이 우선 탐색

DFS(Depth-Find-Search) 깊이 우선 탐색 지난 시간 BFS에 이어 오늘은 DFS에 대해 알아보려고 한다. DFS는 Depth-Find-Search로 깊이 우선 탐색이다. BFS와 다르게 DFS는 깊이를 우선적으로 탐색한다. 즉 최대 깊이까지 재귀적으로 이동한 후 최대 깊이에 도달한 경우 옆으로 이동한다. 또한 BFS에서는 Queue를 사용했다면 DFS에서는 Stack을 사용한다. 이 Stack에 저장된 값이 우리가 원하는 DFS의 탐색 순서이다. 알고리즘 동작 방식 다음과 같다. 1. 특정 정점이 아직 방문하지 않은 정점인 경우 이를 방문처리 해준다. 2. 해당 정점과 연결된 다른 정점에 대해 위 과정을 반복한다. 다음과 같은 그래프가 주어졌을 때 DFS를 적용해보자. ① 시작 정점을 8..