DFS 와 BFS

DFS - depth-first search 깊이 우선 탐색

     트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤

     다시 돌아가 다른 루트로 탐색하는 방식이다.

     일반적으로 재귀호출을 사용하지만 스택으로 구현하기도 한다.

 

     단순 검색 속도 자체는 BFS에 비해서 느리다.

 

 

     장점 

       - 단지 현 경로상의 노드들만을 기얻하면 되므로 저장 공간의 수요가 비교적 적다.

       - 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

 

     단점

       - 해가 없는 경로에 깊이 빠질 가능성이 있다.

       - 얻어진 해가 최단 경로가 된다는 보장이 없다.

출처 : 나무위키

BFS - 넓이 우선 탐색

DFS는 갈림길에서 하나의 길로 들어서서 막다른 길이 나올 때까지 깊게 탐색을 하는 것을 볼 수 있고, BFS는 갈림길에 연결되어 있는 모든 길을 한번씩 탐색한 뒤 다시 연결되어 있는 모든 길을 넓게 탐색하는 것을 볼 수 있다

 

 

BFS - 재귀호출을 이용하여 구현하는 DFS와는 달리 Queue를 사용하여 구현하는 것이 일반적

        배열에서 사용하는 경우 방향 데이터를 이용해 배열의 시작점에서 범위를 넓혀가면서 탐색하는 것