알고리즘 / DFS(Depth First Search), BFS(Breath First Search)

그래프를 탐색하는 방법에 DFS(Depth First Search)와 BFS(Breath First Search)가 있다. 

깊이 우선 탐색인 DFS와 너비 우선 탐색인 BFS를 알아보도록 한다.

 

 

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

트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 대표적으로 백트래킹에 사용된다. 일반적으로 재귀 호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 

갈림길이 나타날 때마다 '다른 길이 있다'는 정보만 기록하면서 자신이 지나간 길을 지워 나간다. 그러다 막다른 곳에 도달하면 직전 갈림길까지 돌아가면서 '이 길은 아님'이라는 표식을 남긴다. 그렇게 갈림길을 순차적으로 탐색해 나가다 목적지를 발견하면 그대로 해답을 내고 종료한다.

 

장점

• 메모리 소모가 적다.
• 목표 노드가 깊은 단계에 있을 경우 해를 빠르게 구할 수 있다.

단점

• 얻어진 해가 최단 경로라는 보장이 없다.
• 해가 없는 경로에 깊이 빠질 가능성이 있다. 

예시

다음과 같은 그래프를 DFS로 구해보겠다. 

 

 

 

다음과 같은 순서대로 탐색하는 것이 DFS이다.

같은 깊이를 탐색할 때는 노드의 번호가 작은 노드부터 반복한다.

 

---

BFS(넓이 우선 탐색, Breath First Search)

가장 가까운 곳들을 먼저 탐색하고, 그 다음 거리에 있는 것들을 탐색하는 방식이다. 

루트에서 시작하여 자식노드를 저장하고 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 저장한다. 자식들을 저장한 노드들을 차례대로 방문한다. 또한 각각의 자식들을 저장한다. 이 과정을 반복하여 모든 노드를 방문하면서 탐색한다.

 

장점

• 최단 경로 찾기가 가능하다.

단점

• 탐색 가지가 급격히 증가하여 메모리 소모가 크다.
• 최악의 경우 모든 경로를 탐색하게 된다. 

예시

 

다음과 같은 그래프를 BFS로 구해보겠다. 

 

 

다음과 같은 순서대로 탐색하는 것이 DFS이다.

같은 깊이를 탐색할 때는 노드의 번호가 작은 노드부터 반복한다.

 

---

 

두 턈색 알고리즘의 과정을 잘 나타내는 그림이다. 

DFS, BFS

BFS 출처 : https://namu.wiki/w/BFS

DFS 출처 : https://namu.wiki/w/DFS