자료구조-알고리즘
[알고리즘] DFS / BFS
DFS / BFS는 그래프 탐색 알고리즘중 하나 탐색이란 수 많은 데이터는 원하는 데이터를 찾는 과정 깊이 우선 탐색(DFS, Depth - First Search) - DFS는 그래프와 트리의 깊은 부분을 우선적으로 탐색하는 알고리즘 - 현재 정점(노드)에서 연결된 정점(노드) 하나를 골라 깊이 끝까지 탐색을 진행하며, 끝까지 진행한 경우 백트래킹을 하여 다음 노드로 탐색을 진행한다. - Stack 혹은 재귀 함수를 이용하여 구현한다. - 모든 정점을 방문할 때 유리하게 사용하며, 경우의수, 순열, 조합 문제에서 많이 사용한다. - 모든 정점을 방문할 필요가 없거나 최단 거리를 구하는 경우에는 너비 우선 탐색(BFS)가 유리하다. 장점 - 현 경로상의 노드들만 기억하므로, 저장공간 수요가 비교적 적다...
