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

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다.

 

대표적인 탐색 알고리즘으로 DFS와 BFS가 있다. 두 알고리즘을 알아보기 전 그래프의 기본 구조를 알아야한다. 그래프는 노드와 간선으로 표현되며 이때 노드를 정점이라고도 한다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면 ' 두 노드는 인접한다' 라고 표현한다.

 

그래프 구조 (출처: '이것이 취업을 위한 코딩테스트다')

 

1. 깊이 우선 탐색 (DFS, Depth-First Search)

: 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

아래의 그림과 같이 루트 노드 혹은 다른 임의의 노드에서 다음 분기로 넘어가기전에 해당 분기를 완벽하게 탐색하는 방법이다. 

DFS 구조 (출처:https://developer-mac.tistory.com/64)

 

DFS의 특징은 다음과 같다.

• 모든 노드를 방문하고자 하는 경우에 선택함
• DFS가 BFS보다 좀더 간단함
• 검색 속도 자체는 BFS 비해서 느림
•  

---

2. 너비 우선 탐색 (BFS, Br-First Search)

: 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래 분기로 이동

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

BFS 구조 (출처:https://developer-mac.tistory.com/64)

BFS의 특징은 다음과 같다.

• 최적해를 찾음을 보장함
• 노드의 수가 늘어나면 탐색해야하는 노드가 많아지기 때문에 비효율적임

---

3. DFS와 BFS의 비교

DFS (깊이우선탐색)	BFS (너비우선탐색)
현재 정점에서 갈 수 있는 노드들까지 들어가면서 탐색	현재 정점에서 연결된 가까운 노드들부터 탐색
스택 또는 재귀함수로 구현	큐를 이용해서 구현

 

두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간복잡도는 동일하다.

 

N은 노드, E는 간선일 때

인접리스트 : O(N+E) 인접행렬 : O(N²)

일반적으로 간선의 크기가 노드 제곱에 비해 상대적으로 적기 때문에 인접 리스트 방식이 효율적임

---

3. DFS와 BFS의 활용

 

1) 그래프의 모든 노드를 방문해야하는 문제

- DFS, BFS 모두 사용 가능

 

2) 최단거리를 구해야 하는 문제

a->b까지 가는데 같은 숫자가 있으면 안된다, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS 사용