dfs는 매 위치마다 세가지 선택을 합니다.

각 세가지 선택마다 세가지 선택을 다시 하고,

이는 깊이가 깊어질수록 기하급수적으로 늘어날겁니다.

물론 방문 체크등을 통해 가지를 줄일수는 있겠지만 그냥 bfs쓰면 스텝마다 방문체크가 더 쉽겠죠.

dfs는 조건에 해당하는 값을 찾았을 때 그게 최단 루트일수도 아닐수도 있습니다. 그래서 다른 가능한 모든 값과 비교하여 최소값을 선정해야 합니다.

bfs는 가장 먼저 찾는 값이 최단 루트이므로 가장 처음 목표에 도달하면 리턴하는 식으로 불필요한 탐색을 줄일 수 있습니다.

두분 모두 감사합니다! 덕분에 이해했습니다!