[Algorithm] DFS / BFS

알고리즘 공부를 하다 보면 DFS와 BFS라는 단어를 자주 접하게 되는데,

이는 트리 구조(또는 그래프)의 탐색과 관련된 알고리즘이다.

 

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

 

깊이 우선 탐색은 미로를 탐색할 때 벽을 따라 한 방향으로 끝까지 간 후 더 갈 수 없을 때 분기점으로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법으로 볼 수 있다.

모든 노드의 방문을 확인하고자 할 때 해당 탐색 방식을 채택하며,

기본적으로 BFS 방식보다 조금 더 느릴 수 있다.

 

(Back-Tracking 과정으로 분기점 방문을 위해 노드를 거슬러 올라가는 과정이 존재)

 

 * DFS 특징 :

• 재귀적으로 호출하는 순환 알고리즘의 형태이다.
• 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS에 속한다.
• 그래프 탐색일 때, 노드의 방문여부를 체크하지 않으면 무한루프에 빠질 위험이 있다.

 

 * DFS 탐색 순서 :

<출처 : https://en.wikipedia.org/wiki/Depth-first_search>

---

2. 넓이 우선 탐색 : BFS (Breath-First Search)

 

루트 노드(또는 특정 노드)에서 출발해서 인접한 노드를 먼저 탐색하는 방법으로,
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

 

트리 구조에서 예시를 보았을 때,

깊이 우선 탐색(DFS)은 노드의 말단 부분까지 탐색, 분기 노드로 Back-Tracking을 반복하는데,

넓이 우선 탐색(BFS)은 같은 Depth의 노드를 모두 탐색하고 다음 Depth로 탐색을 수행한다.

(BFS도 Back-Tracking 구현이 가능하지만 DFS에 비해 상대적으로 많은 메모리를 필요로 한다)

 * BFS 특징 :

• BFS는 재귀적으로 동작하지 않는다.
• BFS는 루트 노드에서 계층적으로 탐색한다.
• BFS는 일반적으로 자료구조 중 하나인 Queue를 사용하여 구현한다.
• 그래프 탐색일 때, BFS도 노드의 방문여부를 체크하지 않으면 무한루프에 빠질 위험이 있다.

 

 * BFS 탐색 순서 :

<출처 : https://en.wikipedia.org/wiki/Breadth-first_search>

 

•  BFS는 최단경로 또는 미로 찾기 같은 알고리즘 구현에 최적화되어 있고 아래 사진을 통해 알 수 있다.

<미로찾기 알고리즘 / 출처 : https://en.wikipedia.org/wiki/Breadth-first_search >