[알고리즘] DFS/BFS 간단 개념 정리

DFS(Depth-First Search)

깊이 우선 탐색은 말 그대로 깊이를 우선으로 하여 최대한 깊이 내려가며 탐색한 뒤 더이상 내려갈 곳이 없을 경우 옆으로 이동하며 탐색을 이어나가는 방법이다.

이는 시작점이 되는 특정 노드에서 시작해서 해당 분기를 모두 탐색하고 다음 분기로 넘어가도록 탐색을 진행한다.

DFS를 사용하는 문제 유형

1. 경로의 특징을 저장해둬야 하는 경우
   BFS는 경로의 특징을 저장할 수 없다.
2. 재귀, 백트래킹을 이용하는 완전 탐색이 필요한 경우
   모든 경우를 끝까지 다 탐색하며 이동한다.

구현

스택 혹은 재귀함수 이용

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있는지 확인
   2-1. 있으면 그 노드를 스택에 넣고 방문 처리
   2-2. 없으면 스택에서 최상단 노드를 꺼냄
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

BFS(Breadth-First Search)

너비 우선 탐색 역시 말 그대로 너비를 우선으로 하여 최대한 넓게 옆으로 이동하며 탐색한 뒤 더이상 갈 곳이 없는 경우 아래로 이동하여 탐색을 이어나가는 방법이다.

이는 시작점이 되는 특정 노드에서 가까운 순으로 노드를 탐색해나가는 것이라고 할 수 있다.

BFS를 사용하는 문제 유형

1. 최단 거리를 구하는 경우
   DFS는 처음 발견한 답이 최단 거리가 아닐 수도 있으므로 최단 거리를 바로 찾을 수 없다.
2. 깊이를 계산해야 하는 경우
   depth 하나씩 다 훑고 지나가며 탐색한다.

구현

큐 이용

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼내고 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

---

출처 및 참고: 이것이 취업을 위한 코딩 테스트다