너비우선탐색

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