[알고리즘] 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

깊이 우선 탐색(Depth First Search)

깊이 우선 탐색이란?

특정노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
➜ 최대한 깊이 내려가고 더 이상 갈 곳이 없을 경우 옆으로 이동
➜ 스택 혹은 재귀함수를 이용하여 구현

탐색 과정(스택)

최대한 밑으로 내려가면서 스택에 쌓고 더 이상 내려갈 수 없게 되면 스택에서 빼면서 옆에서 탐색한다.
...반복...

너비 우선 탐색(Breadth First Search)

너비 우선 탐색이란?

특정노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
➜ 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동
➜ 큐를 이용하여 구현 : deque(양방향 큐)

탐색과정(큐)

노드1부터 시작하여 1을 넣고 한단계 밑으로 내려가 그 단계에 있는 모든 노드들을 차례로 추가할 수 있다.
1과 같은 깊이의 노드가 없기 때문에 한단계 깊이 들어가고 1의 자식들을 하나씩 큐에 추가한다.

큐의 가장 밑부분 노드부터 꺼내고 탐색하여 인접 노드를 추가한다.
...반복...

BFS/DFS 활용한 문제

1. 모든 정점 방문 시: DFS, BFS 상관 없음
2. 경로의 특징을 저장해둬야 하는 문제: DFS
3. 최단거리 구하는 문제: BFS
4. 그래프 규모가 크다면: DFS
5. 그래프 규모가 그리 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않을 때: BFS

출처:https://devuna.tistory.com/32