[알고리즘] 너비 우선 탐색(BFS, Breadth-First Search)이란? 너비 우선 탐색(BFS, Breadth-First Search) 트리나 그래프의 하나의 정점에서 시작해서 정점에 인접한 모든 노드를 먼저 탐색하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법으로 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택합니다. BFS 탐색과정 루트에서 시작한다. 자식 노드들을 [1]에 저장한다. [1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다. [2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다. 위의 과정을 반복한다. 모든 노드를 방문하면 탐색을 마친다. 왼쪽 그림과 같이 하나의 노드의 모든 루트를 깊게(deep) 탐색하고 다음 노드로 넘어가는 깊이우선탐색(DFS)과 오른쪽처럼 달리 동일한 깊.. 알고리즘/이론 2022. 1. 12. 13:48
