[Algorithm] - BFS(Breadth-First Search)
알고리즘 문제에서 자주 다뤄지는 BFS에 대해 알아보자. BFS란? BFS는 말 그대로 너비 우선 탐색으로 깊게 탐색하는 dfs와는 달리 인접한 노드부터 넓게 탐색하는 방법이다. 임의의 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법을 말한다. BFS 사용하는 경우: 두 노드 사이의 최단경로 or 임의의 경로를 찾고 싶을 때 ex) 어떤 지점 a에서 b까지 이동하는 거리를 그래프로 표현한 후 a와 b사이에 존재하는 경로를 찾는 경우 > DFS - 일단 한 경로를 선택하여 끝까지 가보고 막혔다면 다시 이전 분기점으로 돌아와 탐색 > BFS - 시작점과 가까운 곳부터 '차례대로' 살펴보며 탐색 BFS 특징 1️⃣ 재귀적으로 동작 x 2️⃣ 노드 방문 여부를 반드시 검사해야한다. : 방문한 노드를 재방문할..
알고리즘
2023. 4. 22. 03:06