탐색1 [C++] 너비 우선 탐색(BFS : Breath First Search) 이번 시간에는 너비 우선 탐색에 대해 알아보도록 하겠다. 너비 우선 탐색(BFS)은 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘이다. '맹목적인 탐색'을 할 때 사용할 수 있는 탐색 기법으로, '최단 경로'를 찾아준다는 점에서 '최단 길이'를 보장해야할 때 많이 사용한다. 큐를 사용한다. 시작점에서부터 가까운 것부터 탐색을 하겠다는 것이다. 맨 처음에 시작 노드(Start Node)를 큐에 삽입하면서 시작한다. 시작 노드를 방문했다고 표시를 해놓고, 그 이후부터 다음의 알고리즘을 반복한다. 1. 큐에서 하나의 노드를 꺼낸다. 2. 해당 노드에 연결된 노드들 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다. stl queue를 사용해서 구현해본 코드이다. #include #.. 2020. 5. 7. 이전 1 다음