BFS(너비우선탐색) vs DFS(깊이우선탐색)
♠ BFS(Breadth-First-Search) 의 개념 그래프 탐색하나의 정점(노드)로부터 시작하여 차례대로 모든 노드를 한 번씩 방문하는 것. BFS도 그래프 탐색 방법 중 하나이다. BFS는 루트 노드(혹은 다른 임의의 노드)에서 시작하여 인접한 노드를 먼저 탐색하는 방법이다. 따라서 시작 노드로부터 가까운 노드를 먼저 방문하고, 멀리 떨어져있는 노드를 나중에 방문하는 순회 방법이다. ♠ BFS의 특징- BFS는 시작 노드에서 목표 노드까지의 최단 경로를 구하는 데 유용하다. 시작 노드로부터 가까운 노드부터 탐색하기 때문이다. DFS의 경우, 이와 달리 깊이를 끝까지 탐색한 후 옆으로 이동하기 때문에 최단 경로를 구하기 어렵다. - BFS를 구현할 때는 노드 방문 여부를 검사해야 한다. 방문 여..
2024.09.06