깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

1. 깊이 우선 탐색(DFS)_

루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 끝까지 탐색하는 방식

즉, 넓게 탐색하기 전에 깊게 탐색하는 것이다.

 

깊이 우선 탐색의 탐색 방법

DFS는 stack을 이용해서 탐색한다.

0. 방문한 곳 표시하는 곳 필요

1. A를 push하고 시작

2. pop하면서 갈 수 있는 노드가 있다면 push!

3. 2번을 반복

4. 더 이상 갈 수 없다면 pop

5. 2번을 반복

6. 4번을 반복

 

재귀를 이용한 완전탐색 == DFS

 

백트래킹과 DFS의 차이

DFS = 그래프를 완전탐색하는 순회 기법

백트래킹 = 정답을 찾는 도중에 해가 되지 않을 것 같은 경로가 있다면 더 가지 않는 가지치기

• DFS는 단순히 깊이 우선으로 모든 경로를 탐색하는 알고리즘
• 백트래킹은 DFS의 한 형태로, 유망하지 않은 경로를 사전에 차단하여 탐색 효율을 높임

---

2. 너비 우선 탐색(BFS)

루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

즉, 깊게 탐색하기 전에 넓게 탐색하는 것

BFS는 Queue를 이용하여 탐색한다.