Breadth First Search (1) 썸네일형 리스트형 110. Breadth First Search 너비 우선 탐색(Breadth First Search, BFS)은 노드를 탐색하고, 그 노드와 인접한 노드를 탐색하고, 그 노드들과 인접한 노드를 탐색하는 식으로 탐색을 시작한 노드에서 가까운 노드부터 차례로 탐색을 진행하는 탐색 방법이다. 이전에 탐색한 노드들과 인접해서 이후에 탐색할 예정이지만 아직 탐색하지 않은 노드들을 저장하기 위해 보통 큐가 사용된다. 탐색 과정에서 시작 노드에서 각각의 노드까지의 최단 경로의 길이를 알 수 있게 된다. DFS와 마찬가지로 인접한 노드가 여러 개 있을 경우 문제 상황에 맞게 탐색 순서를 정하면 된다. DFS를 설명한 글에 나온 그래프의 노드 $\text{D}$에서 BFS를 시작하면 BFS는 다음과 같이 진행된다. 먼저 노드 $\text{D}$를 방문한다. 노드 $.. 이전 1 다음
