BFS1 [알고리즘]DFS, BFS 이란 너비 우선 탐색(BFS, Breadth-First Search) : 루트 노드(혹은 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 (즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색) 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. 너비 우선 탐색(BFS)의 특징 직관적이지 않은 면이 있다.(BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.) BFS는 재귀적으로 동작하지 않는다. BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.(즉, 선입선출(FIFO) 원칙으로 탐색) ‘Prim’, ‘Dijkstra’ 알고리즘과 유사하다. from collections import dequ.. 2022. 10. 11. 이전 1 다음
