BFS1 너비 우선 탐색(bfs) bfs 대해 알아보기 전에 그래프에 대한 기초가 필요하다. https://hongcode.tistory.com/32를 참고 하자. 너비 우선 탐색(bfs) BFS(Breadth First Search) 이름 뜻 그대로 임의의 정점에서 시작해서 인접한 정점을 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다. 장점 너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장 최단 경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있다. 노드 수가 적고 깊이가 얕은 해가 존재할 때 유리하다. 단점 재귀 호출을 사용하는 DFS와 달리 큐를 이용해 다음에 탐색할 노드들을.. 2022. 3. 11. 이전 1 다음
