지난 포스팅을 통해 DFS를 알아보았으니 형제 탐색법인 BFS를 알아보겠다.BFS 또한 DFS처럼 트리나 그래프를 순회하는 기본 방법 중 하나이다. BFS (Breadth First Search)? BFS는 너비 우선 탐색이다. 시작 노드부터 가까운 노드들을 모두 살펴본 뒤 그 다음 노드들을 탐색한다. 단순하게 생각해서 파원에서 파장이 퍼져나가는 모양을 생각하면 얼추 비슷하다. 특징과 장단점- 연결된 모든 노드를 탐색할 수 있다.- 방문 노드를 기억하고 재방문하지 않는다.- DFS가 스택을 활용하는 것과 다르게 보통 큐를 활용한다.- 최단경로 탐색에 적절하다. 해를 찾고나면 다음 해는 찾을 필요가 없기 때문이다.- 논리 구조가 간단하다.- 해가 깊은 곳에 있으면 탐색에 오랜 시간이 걸릴 수 있다. BF..
