BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)의 차이점과 사용 사례를 설명해주세요.

BFS와 DFS는 그래프 탐색 알고리즘으로, 탐색 순서와 사용하는 자료구조에서 차이가 있습니다.

BFS는 큐를 사용하여 현재 노드와 연결된 모든 노드를 먼저 탐색합니다. 마치 물이 퍼져나가듯이 넓게 탐색하죠. 그래서 최단 경로를 찾는 문제에 유용합니다. 예를 들어, 지도에서 두 지점 사이의 최단 거리를 구할 때 사용할 수 있습니다.

반면 DFS는 스택을 사용하여 한 노드에서 최대한 깊숙이 탐색한 후, 더 이상 갈 곳이 없으면 이전 노드로 돌아가 다른 경로를 탐색합니다. 미로 찾기나, 그래프 내의 모든 경로를 탐색하는 문제에 적합합니다.

메모리 사용량 측면에서는, BFS는 큐에 많은 노드를 저장해야 할 수 있어 DFS보다 메모리를 더 많이 사용할 수 있습니다. DFS는 재귀 호출을 사용하므로 스택 오버플로우에 주의해야 합니다.