알고리즘

DFS, BFS

• 인접 행렬 구현 시, O(V^2)
• 인접 리스트 구현 시, O(V + E)

1) DFS (Depth First Search, 깊이 우선 탐색)

• 재귀함수 or 스택으로 구현
• 가능한 최대 깊이까지 탐색하는 방식
  
  

① 장점

• 큐에 탐색할 노드들을 저장하는 BFS에 비해, 메모리 소비가 적음

② 단점

• 최적 해의 탐색을 보장하지 못함
• Worst Case의 경우, 가능한 모든 경로를 탐색함

2) BFS (Breadth First Search, 너비 우선 탐색)

• 큐로 구현
• 현재 노드와 가까운 노드부터 탐색하는 방식
• 주로, 최단 경로 (최적 해)를 탐색하는 경우 사용
  
  

① 장점

• 최적 해의 탐색이 보장됨

② 단점

• 노드의 수가 많을 수록 탐색 해야하는 노드가 많아짐
• 큐에 탐색할 노드들을 저장하므로, 노드의 수가 많을 수록 메모리 소비가 큼

Question) "DFS와 BFS에 대해 설명 해주세요."

DFS와 BFS는 그래프 탐색 알고리즘 입니다.

• DFS는 재귀함수 또는 스택으로 구현하며, 가능한 최대 깊이까지 탐색하는 방식 입니다.
  장점은 큐에 탐색할 노드들을 저장하는 BFS에 비해, 메모리 소비가 작습니다.
  단점은 최적 해의 탐색을 보장하지 못하고,
  Worst Case의 경우, 가능한 모든 경로를 탐색 합니다.
  
  
• BFS는 큐로 구현하며, 현재 노드와 가까운 노드부터 탐색하는 방식 입니다.
  장점은 최적 해의 탐색이 보장 됩니다.
  단점은 노드의 수가 많을 수록 탐색 해야하는 노드가 많아집니다.
  또한 큐에 탐색할 노드들을 저장하므로, 노드의 수가 많을 수록 메모리 소비가 큽니다.