음… ㅋㅋ 면접보고 왔는데 bfs/dfs의 장단점을 물어보셨다. 나는 뭔지만 공부했고 구현해보는 데에만 집중한 나머지 장단점이 뭔지 궁금해하지 않았다는 사실…!😱 그래서 오늘 공부해보려고 한다.

BFS의 장단점? 🧐

  1. 장점
  • 경로가 여러 개인 경우에도 최적해를 보장한다.
  • 최단 경로가 존재한다면 최적해를 찾을 수 있다.
  • 왜?: 한 노드의 자식들을 모두 탐색하기 때문에.
  1. 단점
  • 노드의 수가 많아지면 탐색해야하는 노드의 수도 많아진다.

DFS의 장단점? 🧐

  1. 장점
  • 최선의 경우 가장 빠름.
  1. 단점
  • 답이 아닌 경로가 깊다면 해를 구하는 데에 오래 걸린다.
  • 왜?: 다시 돌아와서 탐색해야하기 때문에.

💚 딱히 장단점은 중요하지 않은 것 같다. 최단 경로 찾기에는 어쨋든 최적해를 보장해주는 BFS를 써야하지않을까? DFS는 SCC를 찾는 데 사용한다고 한다.