4. BFS와 DFS의 장단점, 차이

⭕ DFS 장점

• 현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용합니다.
• 찾으려는 노드가 깊은 단계에 있는 경우 BFS 보다 빠르게 찾을 수 있습니다.

❌ DFS 단점

• 해가 없는 경로를 탐색 할 경우 단계가 끝날 때까지 탐색합니다. 효율성을 높이기 위해서 미리 지정한 임의 깊이까지만 탐색하고 해를 발견하지 못하면 빠져나와 다른 경로를 탐색하는 방법을 사용합니다.
• DFS를 통해서 얻어진 해가 최단 경로라는 보장이 없습니다. DFS는 해에 도착하면 탐색을 종료하기 때문입니다.

 
 

⭕ BFS 장점

• 답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장한다.
• 최단 경로가 존재하면 깊이가 무한정 깊어진다고 해도 답을 찾을 수 있다.

❌ BFS 단점

• 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
• 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
• 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

(Socurce: Wiki)
 
 
 
 
 

🌺 DFS vs BFS 탐색 차이

Figure 2. 트리에서 DFS, BFS 탐색 차이

• DFS는 스택(혹은 재귀), BFS 큐를 사용합니다.
• BFS는 재귀적으로 동작하지 않습니다.

But 문제를 푸는 입장에서는 다음과 같은 구분점이 필요합니다.

• 최단 거리 문제를 푼다면 BFS를 사용합니다.
• 이동할 때마다 가중치가 붙어서 이동한다거나 이동 과정에서 여러 제약이 있을 경우 DFS로 구현하는 것이 좋습니다.