자료구조와 알고리즘 - BFS, DFS

본 내용은 프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 토대로 작성하였습니다.

1. BFS, DFS란?

• BFS(Breadth-First Search)
  • 너비 우선 탐색
  • 그림판의 페인트
• DFS(Deptsh-First Search)
  • 깊이 우선 탐색
  • 최단거리

2. BFS

• 그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘
• Queue를 이용하여 구현
• 시작 지점에서 가까운 정점붜 탐색
• V가 정점의 수, E가 간선의 수일 때 BFS의 시간복잡도는 O(V + E)

3. DFS

• 최대한 깊은 정점부터 탐색하는 알고리즘
• Stack을 이용하여 구현
• 시작 점정에서부터 깊은 것부터 찾음
• V가 정점의 수, E가 간선의 수일 때 DFS의 시간복잡도는 O(V + E)

Reference

프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript