[PS/Tip] BFS vs DFS

이 내용에 대해선 앞으로 보완해나갈 예정입니다. 많은 문제를 풀어보면서 최대한 정리해보겠습니다.

BFS vs DFS

BFS

• BFS는 시작 정점에서 가까운 정점을 찾는데 적합하다
  • 큐를 이용하여 가까운 원소들부터 탐색하기 때문
• 최단 거리 경로를 찾는데 적합하다.
  • BFS에서는 특정 정점을 방문할 경우, 시작 정점에서 해당 정점까지의 최단 거리 경로가 보장된다.
• BFS는 현재 경계에서 인접한 모든 정점을 방문하므로 BFS에 의해 생성된 검색 트리는 짧고 넓은 편이며, 많은 메모리를 필요로 한다

DFS

• DFS는 대체로 시작 정점에서 멀리 있는 정점을 찾을 때 적합하다.
• 재귀적인 풀이 방식에 적합하다 (후입선출의 스택 구조를 사용하기 때문)
• 백트래킹 방식의 PS 풀이에서 적합하다.
• 모든 경우를 하나 하나 다 탐색해야 하는 경우 적합하다
• DFS에 의해 생성된 검색 트리는 길고 좁은편이며, 상대적으로 적은 메모리를 필요로 한다.

 

이 외에도 BFS, DFS를 변형한 알고리즘(ex. 프림 알고리즘) 등이 존재하기 때문에, 주어진 상황에 가장 적합한 알고리즘을 선택!