DFS와 BFS 언제 쓸까?

dfs(깊이 우선 탐색)과 bfs(너비 우선 탐색) 언제 사용하는 게 유리할까?

DFS와 BFS의 차이점

탐색 순서

DFS는 한 경로를 따라 최대한 깊게 들어가서 더 이상 갈 곳이 없을 때까지 탐색한다. 그래서 한 경로의 끝까지 탐색한 후 다음 경로로 이동한다.

BFS는 한 노드에서 시작하여 인접한 모든 노드를 먼저 탐색한 후에 그 다음 단계의 노드로 이동한다. 즉, 한 레벨씩 탐색을 진행한다.

탐색 속도

DFS는 한 경로를 따라 깊이 우선적으로 탐색하기 때문에, 최악의 경우에는 모든 노드를 한 경로로 따라가게 될 수 있다. 따라서 트리의 깊이가 매우 깊은 경우에는 DFS가 더 많은 시간이 걸릴 수 있다.

BFS는 레벨별로 탐색하기 때문에, 최단 경로를 찾는 문제에 적합하다. 일반적으로 DFS보다는 시간이 더 걸리지만, 최단 경로를 보장한다.

메모리 사용

DFS는 스택을 사용하여 탐색 경로를 저장하므로 메모리 사용량이 적다. 그러나 트리의 깊이가 깊을 경우에는 스택 오버플로우가 발생할 수 있다.

BFS는 큐를 사용하여 탐색할 노드를 저장하므로 메모리 사용량이 더 많을 수 있다. 그러나 보통 효율적인 메모리 사용을 위해 인접 리스트 대신 인접 행렬을 사용하는 것이 좋다.

• 인접 리스트

const graph = new Array(numVertices).map(() => []);

• 인접 행렬

const graph = Array.from({ length: M }, () =>
    Array.from({ length: N }, () => 0)
  )

DFS가 유리한 문제

1. 경로 찾기: 단순히 두 지점 간의 경로가 존재하는지 여부를 찾을 때 DFS가 유용하다.

• 목표 지점을 찾은 후에는 빠르게 종료 가능하다.

2. 깊이 우선 탐색이 필요한 경우: 그래프에서 깊이를 우선적으로 탐색해야 하는 경우 DFS가 유용하다.

• ex. 트리에서 전위/중위/후위 순회를 수행할 때

3. 해결책의 수가 많은 경우: DFS는 해결책의 수가 많은 경우에 유용하다.

BFS가 유리한 문제

1. 최단 경로 찾기: 그래프에서 두 지점 사이의 최단 경로를 찾아야 할 때 BFS가 유용하다.

• BFS는 너비 우선 탐색이므로 최단 경로를 찾는 데 효율적입니다.

2. 최소 비용 문제: 경로의 가중치가 주어진 경우에는 BFS가 최소 비용 경로를 찾는 데 효과적이다.

• 모든 경로를 탐색하지 않고 먼저 발견된 경로가 최단 경로임을 보장합니다.

3. 최단 경로가 유일한 경우: 최단 경로가 유일한 경우 BFS가 가장 효율적이다.

• 이 경우 BFS는 최단 경로를 찾는 데 시간복잡도가 더 낮습니다.

4. 상태 공간 탐색: 상태 공간에서 최소 이동/변경 횟수를 찾는 문제에는 BFS가 적합하다.

• ex. 8 퍼즐, 스도쿠 등의 문제