BFS vs DFS 어떤 기준으로 선택하나?

코테 스터디에서 프로그래머스 Lv.3 미로 탈출 명령어 를 BFS로는 안되는지에 대해 얘기가 나왔다. DFS로는 풀었지만, BFS로는 어떻게 해야할지 몰랐다.

BFS와 DFS의 기준이 무엇인가..? 가 문득 스쳐지나가서 마지막으로 확실히 하고 가려고 한다.

대체 DFS랑 BFS는 어떤 기준으로 선택해야 하나?

DFS

1. 연결된 그래프를 완전 탐색하는데 활용
2. 모든 경우를 하나하나 모두 탐색을 해야 될 경우
   (조합, 순열 등 모든 경우의 수를 다 찾아야 할 때)
3. 위의 개념과 결부된 깊이 우선 탐색이라는 개념을 가진 순열, 조합 구현에 활용

BFS

1. 연결된 그래프를 완전탐색하는데 활용
2. depth(깊이) 를 계산해야되는 문제에 활용
   (최단경로의 길이 == depth(깊이))
3. 가중치가 같은 그래프에서 최단거리를 찾는데 활용

추가 정보

DFS와 BFS는 인접 행렬과, 인접 리스트로 구현을 한다.

• 인접 행렬일 때 : 둘 다 시간복잡도 $O(V^2)$
• 인접 리스트일 때 : 둘 다 시간복잡도 $O(V+E)$

근데, 문제에서 BFS로 풀면 최악의 경우 약 9000ms가 나온다.
DFS는 약 100 ~ 200ms 인데... 왜 다를까?

나중에 더 찾아보고 추가해야겠다..