반응형
⭕ 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로 구현하는 것이 좋습니다.
반응형
'Programming > Coding Test' 카테고리의 다른 글
[C++] 백준 2573 빙산 - 테스트 케이스 (0) | 2020.11.15 |
---|---|
런타임에러 1 - return 1 return 0 return -1 의미 (0) | 2020.11.14 |
3. BFS Reference Code - 지도 유형,백준 2178,2667,2468,1697,5014 (0) | 2020.11.03 |
2. BFS Referenct Code - 노드 유형, 백준 1260, 2606, 2644 (0) | 2020.11.02 |
1. DFS Reference Code - 노드 유형, 백준 1260, 10971 (0) | 2020.11.02 |