BFS, DFS

해당 내용은 프로그래머스 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 공부하며 정리한 내용입니다.

1. BFS, DFS란?
   BFS : 너비 우선 탐색
   DFS: 깊이 우선 탐색

2. 특징

BFS

• Queue를 이용하여 구현할 수 있다.
• 시작 지점에서 가까운 정점부터 탐색한다.
• V가 정점의수, E가 간선의 수일 때 BFS의 시간복잡도는 O(V+E)다.

DFS

• Stack을 이용하여 구현할 수 있다.
• 시작 정점에서 깊은 것 부터 찾는다.
• V가 정점의 수, E가 간선의 수일 때 BFS의 시간복잡도는 O(V+E)다.

3. 코테
   핵심키워드 : 노드, 간선, 가장
   대표문제: 가장 먼 노드