[알고리즘] DFS (깊이 우선 탐색) 와 BFS (너비 우선 탐색), 그리고 Binary Search(이진 탐색)

💡 대부분의 내용을 Do it! 알고리즘 코딩테스트 with JAVA 강의를 참고하여 정리하였습니다.

 

 

DFS (Depth - First Search)

---

DFS (깊이 우선 탐색)은 그래프 완전 탐색 기법 중 하나이다.

그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른쪽 분기로 이동하여 다시 탐색한다. (최대 깊이까지 탐색한 후 다음으로 넘어간다!)

 

특징

• 재귀함수로 구현한다. 이때, stack overflow에 유의해야 한다.
• 스택 자료구조를 이용한다.

 

시간 복잡도

O(V + E)

O(노드 수 + 엣지 수)

 

핵심 이론

• 노드 방문 여부를 체크할 배열이 필요하다.
  • 한 번 방문한 노드는 다시 방문하면 안 되기 때문이다. 중복 방문 불가!!
• 그래프(데이터를 담는 자료구조)는 인접 리스트로 표현한다.
• 스택 성질을 가지는 재귀 함수로 주로 구현한다.
  • DFS의 탐색 방식은 후입선출(LIFO) 특성을 가지기 때문이다.

 

 

BFS (Breadth - First Search)

---

BFS (너비 우선 탐색)은 그래프 완전 탐색 기법 중 하나이다.

시작 노드에서 출발하고, 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

 

특징

• 선입선출(FIFO) 탐색이다. 
• 큐(queue) 자료구조를 이용한다.

 

시간 복잡도

 

O(V + E)

O(노드 수 + 엣지 수)

 

DFS와 BFS의 시간 복잡도는, 두 방식 모두 조건 내의 전체 노드를 탐색한다는 점에서 동일하다. 하지만, 일반적으로 DFS를 재귀함수로 구현한다는 점에서 BFS가 조금 더 빠르게 동작한다.

 

핵심 이론

DFS와 동일한 특징이다.

• 방문했던 노드는 다시 방문하지 않는다.
• 그래프(데이터를 담는 자료구조)는 인접 리스트로 표현한다.

DFS와의 차이점은, 스택이 아닌 큐를 사용한다는 것이다.

 

 

 

표로 나타내보면 다음과 같다.

	DFS (깊이 우선 탐색)	BFS (너비 우선 탐색)
탐색 방법	시작 노드 기준 최대 깊이까지 방문하면서 탐색	시작 노드 기준 가장 가까운 노드부터 방문하면서 탐색
구현 방법	스택 or 재귀함수	큐
시간 복잡도	O(V + E)

 

 

 

❓ 둘 중 어느 것을 사용해야 할까?

1. 그래프의 모든 정점을 방문하는 문제

 DFS, BFS 둘 다 사용 가능

 

2. 경로의 특징을 저장해두어야 하는 문제

ex) 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때
DFS 사용 (BFS는 경로의 특징을 가지지 못한다)

 

3. 최단거리를 구하는 문제

ex) 미로 찾기 등 최단 거리를 구해야 할 때
BFS 사용
(DFS로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있다. 반면, BFS는 현재 노드부터 가까운 곳부터 찾기 때문에 경로 탐색 시 먼저 찾아지는 해답이 곧 최단거리이다.)

 

📌 검색 대상 그래프가 클 때 -> DFS 고려
📌 검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 멀지 않을 때 -> BFS 고려

 

 

 

Binary Search (이진 탐색)

---

Binary Search(이진 탐색)은 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘이다.

데이터의 중앙값과 찾고자 하는 값을 비교하여 데이터의 크기를 절반씩 줄이면서 원하는 값을 찾는다.

 

정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘이다.

 

구현 및 원리가 비교적 간단하기 때문에, 코딩테스트에서는 주로 부분 문제로 요구하는 영역이다.

 

 

시간 복잡도

O(logN)

 

 

이진탐색은 log(N)번의 연산으로 원하는 데이터의 위치를 찾을 수 있다. 

하지만 이진탐색은 반드시 데이터가 정렬되어 있는 상태여야 한다는 것에 주의하자!

 

 

---

Reference

 

https://devuna.tistory.com/32

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