DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

▲트리 구조에서의 BFS와 DFS 표현 ( source : http://mishadoff.com/blog/dfs-on-binary-tree-array/ )

너비 우선적으로 검색하면 너비우선탐색 (Breadth First Search)
깊이 우선적으로 검색하면 깊이우선탐색 (Depth First Search)

 

▲Breadth First Search로 타일을 검사시, 검사 시작지점 인근부터 검사, 전부 체크 후 퍼져나감

▲Depth First Search로 타일을 검사시, 검사 시작지점서 의도한 방향으로 깊게 검사 후에 다음 검색

---

어차피 조건내의 모든 노드를 검색한다는점이 같기때문에 시간복잡도는 동일합니다만
공간복잡도는 깊이우선탐색의 경우, 본인이 지금 파고들어가고 있는 루트만 신경쓰는 반면
너비우선탐색은 최악의경우 모든 노드 -1 개까지도 들고 있을수 있는 상황이 나오는 차이가 있습니다.

 

알기쉽게 BigO로 표현하자면
시간복잡도 : 너비우선, 깊이우선 둘 다 O(n)
공간복잡도 : 너비우선 : O(n), 깊이우선 O(d)

 

위에서 나오는n은 최대 노드 수를 상징하며, 공간복잡도에서의 d는 최대 깊이입니다.

---

DFS와 BFS는 어느게 정답이 있다기보단 용도가 다릅니다.

 

- 위에 언급한 공간복잡도 때문에, 검색대상그래프가 정말 크다면 DFS를 고려
- 검색대상의 규모가 크지 않고, 검색시작지점으로부터 원하는 대상이 별로 멀지 않다면 BFS
- 깊이우선탐색으로 경로를 검색한다 가정시 처음으로 발견되는 해답이 최단거리가 아닐수 있음
- 너비우선탐색으로 경로를 탐색시 먼저 찾아지는 해답이 곧 최단거리임
- 보통 DFS는 스택,재귀함수를 이용해 구현가능, BFS는 큐를 이용하여 구현

 

---

필요에 따라 다르게 사용하면 될 거 같습니다.
얼마전에 소개해드린 Flood Fill 알고리즘 또한 같은 로직이어도
컨테이너로 스택을 사용하면 백트래킹 기능을 가진 DFS가 되고,
컨테이너로 큐를 사용시 먼저 들어왔던거부터 처리하기에 BFS가 됩니다.