[알고리즘 개념] - DFS와 BFS 구분 기준 정하기!

BFS와 DFS란?

DFS란?
BFS란?

DFS와 BFS 비교

DFS

• 현재 노드에서 최대한 들어갈 수 있는 깊이까지 들어가서 탐색하는 방식.
• 스택 또는 재귀함수로 구현

BFS

• 현재 노드에 연결된 가까운 인접 노드부터 탐색하는 방식.
• 큐로 구현

시간 복잡도

두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하지만 일반적으로 DFS를 재귀 함수로 구현한다는 점에서 DFS보다 BFS가 조금 더 빠르게 동작한다고 생각하면 됩니다.

일반적으로 인접 리스트와 인접 행렬 중 리스트가 효율적이다 라는 점을 알면 됩니다.

N이 노드의 갯수, E가 간선의 갯수 일 때,
인접 리스트 : O(N+E)
인접 행렬 : O(N^2)

💡 문제 유형 분류

• 그래프의 모든 노드를 방문하는 것이 목적인 문제.

  DFS 또는 BFS 사용

• 경로의 특징을 저장해둬야 하는 문제.

  DFS 사용
  예를 들어 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안된다는 문제가 있다. 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다.(BFS는 경로의 특징을 가지지 못함)

• 최단거리(최소 깊이)를 구하는 문제.

  BFS 사용
  이는 DFS로 경로 탐색 시 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, BFS는 현재 노드부터 가까운 곳부터 찾기 때문에 경로 탐색 시 먼저 찾아지는 해답이 곧 최단 거리이기 때문이다.