BFS로 풀었을 때, 유리한 상황
- 현재 나의 위치에서 가장 가까운 노드를 먼저 방문하는 알고리즘.
- 따라서, 미로 탐색과 같은 알고리즘은 최단 거리만을 가지고 탈출하기 때문에 BFS가 유리.
- 최단 거리(최소 횟수)를 찾는 문제, 임의의 경로를 찾는 문제에서 주로 사용.
- ex)
- DFS: 전국의 모든 도로를 다 살펴봐야할 수도 있다.
- BFS: 서울과 인접한 도로먼저 탐색.
DFS로 풀었을 때, 유리한 상황
- but, 미로탐색을 진행하는데 이동할 때마다 가중치가 붙거나 이동 과정에서 여러 제약이 있을 경우, DFS가 유리.
- why? DFS로 접근하면 탐색 시간은 더 걸리지만, 가중치에 대한 변수를 지속해서 관리할 수 있다는 장점이 있어서 코드 구현에 더 편리함.
- 모든 노드를 방문해야할 때나 재귀적으로 계속 호출해야하는 문제일 경, DFS를 활용.