DFS(Depth-Frist Search)
깊이 우선 탐색
루트 노드에서 시작해 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하는 기법
모든 노드를 방문하고자 하는 경우에 사용
단순 검색 속도 자체는 BFS에 비해 느림
특징
자기 자신을 호출하는 순환 알고리즘의 형태
구현할떄 어떤 노드를 방문했었는지 여부를 반드시 검사해야함
구현 방법
순환 호출 이용
명시적인 스택 이용
시간 복잡도: O(V+E)
공간 복잡도: O(h)
BFS(Breadth-First Search)
너비 우선 탐색
루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
두 노드 사이의 최단 경로 or 임의의 경로를 찾고 싶을 때 주로 사용
DFS에 비해 좀 더 복잡함
특징
직관적이지 않음
재귀적으로 동작하지 않음
DFS와 마찬가지로 구현할 때 어떤 노드를 방문했었는지 여부를 반드시 검사해야함
방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐를 사용 (선입선출 원칙)
Prim, Dijkstra 알고리즘과 유사함
구현 방법
자료구조 큐를 이용
시간 복잡도 : O(V+E)
공간 복잡도 : O(w)
(w: 최대 레벨의 노드 수)
BFS와 DFS의 차이점에 대해서 설명해주세요
BFS는 너비를 우선으로 탐색하며 같은 레벨의 노드를 모두 탐색한 후에 다음 레벨로 이동합니다. 그리하여 최단경로를 찾을 때 주로 사용하며, 큐를 사용하여 노드를 저장하므로 공간복잡도는 레벨의 노드 수에 의해 결정됩니다. DFS는 깊이를 우선으로 탐색하며 한 분기를 따라 최대한 깊이 들어가서 더이상 갈곳이 없으면 백트래킹을 합니다. 재귀나 스택을 사용하며, 깊은 경로나 사이클을 찾을 때 주로 사용하며, 공간 복잡도는 깊이에 의해 결정됩니다.
