🔴 DFS와 BFS
DFS와 BFS는
그래프 알고리즘에서 사용되는 주된 탐색 방법이다. 그래프의 모든 노드를 탐색하고 정보를 찾는데 사용된다. 이 알고리즘들의 원리와 장단점들에 대해서 알아보자
✔ DFS
DFS의 원리
그림과 같이 DFS는 노드를 선택하고 최대한 깊은 곳까지 탐색한 이후 갈곳이 없다면 되돌아가 그 곳에서의 깊은 곳까지 탐색하는 방법이다.
위의 gif를 보면 이러한 형태로 나타낼수 있다.
처음 1에 연결된 노드는 2,4,8이고 낮은 순서로 2부터 탐색한다. 그리고 2가 쌓이고 2에 연결된 노드 3이 쌓인다. 3에 연결된 노드 중 탐색하지 않은 노드는 없기 때문에 다시 빠져 나가고 똑같은 이유로 2도 빠져 나간다. 그 다음 1에서 탐색되지 않은 4가 들어오고 이 과정을 반복하는 것이다. 이 때문에 스택 방식(선입선출)으로 구현한다.
✔ BFS
DFS처럼 노드를 탐색하지만 깊이를 우선으로 탐색하는 과정이 아니라 너비로 우선 탐색하는 과정이다.
처음 1노드가 있는 상태에서 1은 제거하고 1과 연결된 모든 노드를 넣는다. 그 다음 맨 앞에 있는 2노드를 제거하고 2와 연결된 노드를 넣는다. 이 과정을 계속해서 반복하는 것이다. 선입선출의 큐를 이용한 방식이다.
✔ 언제 DFS와 BFS를 사용해야 할까??
-
모든 노드를 방문하는 것이 문제인 경우
단순히 모든 노드를 방문해야하는 경우 두 방법 중 어느 것을 사용해도 상관이 없다. -
검색 대상 그래프의 규모가 큰 경우
검색대상의 그래프가 크다면 DFS를 고려하는 편이 좋으며, 검색 규모가 크지 않고, 검색 대상과 노드가 멀지 않다면 BFS -
경로의 최단거리를 구하는 경우
미로 찾기 등 최단 거리를 구해야 하는 경우 BFS가 유리하다. BFS는 현재 노드부터 가까운 곳부터 찾기 때문에 경로 탐색 시 먼저 찾아지는 답이 최단거리이다.
👍올바른 피드백은 언제든지 환영입니다~!
