📍 BFS란?
: Breadth-First Search(너비우선탐색)으로,
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색한다.
-> 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.
1. BFS vs DFS
(1) 깊이 우선 탐색 DFS
- 노드 간의 "하나 하나" 모든 관계를 알아야 할 때 사용한다.
- 재귀적인 특성을 가진다.
(2) 너비 우선 탐색 BFS
- 노드의 최단 경로를 찾을 때 사용한다.
- 깊이 관련 특성을 가진다.
- 재귀적인 특성을 가지고 있지 않다.
- 선입선출(FIFO) 원칙으로 탐색 -> 큐 사용
2. BFS 해결 방식
대부분 큐(Queue)를 사용하여 해결한다.
시작 노드를 큐에 삽입
큐에서 노드를 꺼내서 처리
방문한 노드를 기록
큐가 빌 때까지 위의 과정을 반복
출처 : https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
3. 시간복잡도
- BFS의 시간 복잡도 : O(V + E)
노드 수(V): 그래프에 있는 노드(정점)의 수
간선 수(E): 그래프에 있는 간선(엣지)의 수
