09-05. DFS와 BFS

Q. DFS와 BFS의 기본 개념과 차이점에 대해서 설명해주세요

DFS는 깊이 우선 탐색이라고 하며 한 경로를 끝까지 탐색한 후 다른 경로를 탐색하는 방식으로, 스택 또는 재귀를 사용합니다. BFS는 너비 우선 탐색이라고 하며 모든 인접 노드를 먼저 탐색한 후, 그 다음 레벨로 이동하는 방식으로, 큐를 사용합니다.

---

Q. DFS와 BFS의 시간 복잡도는 각각 어떻게 되며, 각각의 알고리즘이 적합한 상황은 언제인가요?

DFS를 인접 리스트를 사용하면 각 노드를 한 번씩 방문하고, 각 간선을 한 번씩 탐색하기 때문에 O(V+E) 의 시간복잡도를 가지며, BFS는 각 노드를 한 번씩 방문하고, 각 간석을 한 번씩 큐에 넣고 탐색하기 때문에 DFS와 동일한 시간 복잡도를 가집니다. DFS는 경로 탐색이나 사이클 검출과 같이 깊이를 우선으로 탐색하는 문제에 적합하고, BFS는 최단 경로 탐색이 적합합니다.

---

Q. DFS를 재귀적으로 구현할 때 주의해야 할 사항이 있나요?

DFS를 재귀적으로 구현할 때, 재귀호출이 너무 깊어지면 스택 오버플로우가 발생할 수 있습니다. 이 문제를 방지하기 위해, 재귀 깊이가 너무 깊어지지 않도록 문제의 범위를 제한하거나, 필요에 따라 반복문을 사용한 스택기반의 DFS 구현을 고려할 수 있습니다. 또한, 그래프의 노드가 많을 경우, 방문한 노드를 추적하기 위한 방문 배열이나 세트를 사용해 무한 재귀를 방지해야 합니다.