Breadth-First Search

루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법 특징 장점 노드 수가 적고 깊이가 얕은 경우 빠르게 동작 가능 단순 검색 속도가 깊이 우선 탐색 (DFS) 보다 빠름 너비를 우선 탐색하기에 답이 되는 경로가 여러 개인 경우 최단 경로임을 보장 최단 경로가 존재한다면 어느 한 경로가 무한히 깊어진다해도 최단 경로를 반드시 찾을 수 있음 단점 재귀 호출의 DFS 와 달리 큐에 다음으로 탐색할 정점들을 저장해야 하므로 저장 공간이 많이 필요함 노드 수가 늘어나면 탐색해야 하는 노두 또한 많아짐 노드 탐색 순서 루트 노드에서 시작한다. 루트 노드와 인접하고 방문된 적 없으며, 큐에 저장되지 않은 노드를 큐에 넣는다. 큐에서 노드를 꺼내어 그와 인접한 노드들 중 방문된 적 없으며, 큐에 저장되지 않는 노..