[알고리즘] DFS / BFS

DFS / BFS는 그래프 탐색 알고리즘중 하나

탐색이란 수 많은 데이터는 원하는 데이터를 찾는 과정

 

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

- DFS는 그래프와 트리의 깊은 부분을 우선적으로 탐색하는 알고리즘

- 현재 정점(노드)에서 연결된 정점(노드) 하나를 골라 깊이 끝까지 탐색을 진행하며, 끝까지 진행한 경우 백트래킹을 하여 다음 노드로 탐색을 진행한다.

- Stack 혹은 재귀 함수를 이용하여 구현한다.

- 모든 정점을 방문할 때 유리하게 사용하며, 경우의수, 순열, 조합 문제에서 많이 사용한다.

- 모든 정점을 방문할 필요가 없거나 최단 거리를 구하는 경우에는 너비 우선 탐색(BFS)가 유리하다.

 

 

장점

- 현 경로상의 노드들만 기억하므로, 저장공간 수요가 비교적 적다.

- 목표 노드가 깊은 단계에 있을 경우 빠른 답을 구할 수 있다.

 

단점

- 답이 없는 경로의 깊이가 깊을 경우 탐색 시간이 오래 걸린다.

- 깊이가 무한히 깊어질 경우 StackOverflow의 위험이 있다. (깊이 제한을 두는 방법으로 해결)

 

시간복잡도

- 인접 행렬의 경우 O(N^2)

- 인접 리스트의 경우 O(N+E) 

너비 우선 탐색(BFS, Breadth - First Search)

- BFS는 너비를 우선으로 하여 탐색을 수행하며 '맹목적인 탐색'을 하고자 할 때 사용할 수 있는 탐색 기법이다.

- BFS는 '최단 경로'를 찾아준다는 점에서 최단 길이를 보장해야 할 때 사용된다.

- Queue를 이용하여 지금 위치에 갈 수 있는 정점을 모두 Queue에 넣는식으로 구현한다.

 

 

장점

- 너비를 우선 탐색하므로 답이 되는 경로가 여러개인 경우일지라도 최단 경로를 얻을 수 있다.

- 경로가 무한히 깊어져도 최단 경로를 반드시 찾을 수 있다.

 

단점

- DFS와 달리 큐를 이용하여 다음에 탐색할 정점들을 저장하므로 더 큰 저장공간이 필요하다.

 

시간복잡도

- 인접 행렬의 경우 O(N^2)

- 인접 리스트의 경우 O(N+E)