BFS와 DFS, 둘 중 무엇을 언제 어떤 경우에 사용해야할까?

 

많은 사람들이 맞닥뜨린 문제에 BFS를 사용해야할지 DFS를 사용해야 할지 고민할거라고 생각합니다. 저는 둘이 계산 결과가 같으니 내가 편한것을 사용하면 되지 않을까? 라고 생각하던 때도 있었습니다.

 

하지만 둘의 계산 결과는 "같을 수도 있고, 다를 수도 있"습니다.

 

언제 BFS를 써야할까요?

BFS는 개울가에 돌을 던지면 돌을 중심으로 물결이 퍼지듯. "가까운 곳부터 탐색을 바깥으로 퍼져나가는 느낌"이 강합니다.

 

• 사용 기준
  • 최단 거리 (-> 거리 배열로 몇 칸 만에 목적지에 도달할지)
  • 시간에 따른 변화 (-> 전염병, 불, 얼음의 녹음 등)
  • 단계별로 진행 되는 경우
• 대표 기출 예시
  • 바이러스 확산
  • 얼음이 녹는 순서
  • 로봇이 목적지까지 최소 거리로 이동

---

언제 DFS를 써야할까요?

 

DFS는 한 방향으로 끝~~ 까지 가보자는 느낌이 강합니다.

 

• 사용 기준
  • 영역의 수나 크기 (-> 덩어리 갯수 세기)
  • 백트래킹
  • 조합/순열/완전탐색
• 대표 기출 예시
  • 안전영역 개수 세기
  • 연산자 끼워넣기
  • 색칠된 영역의 넓이 계산

---

구분	BFS (너비우선탐색)	DFS (깊이우선탐색)
탐색 순서	가까운 노드부터	한 경로를 끝까지
자료 구조	큐(deque)	재귀 혹은 스택
사용 목적	최단 거리, 시간의 흐름	완전 탐색, 백트래킹, 경우의
사용 예	미로 내 최단 거리, 전염, 물 퍼짐	영역 개수 세기, 조합/순열, 경로찾기

 

경우에 따라 BFS나 DFS는 둘다 쓸 수도 있고 정답도 같을 수 있습니다. 하지만 

• BFS는 더 많은 메모리를 사용한다는 점 ( 큐 유지 )
• DFS는 깊이가 깊어질 수록 recursion limit 이슈 생길 수 있다는 점

이런 특징들을 고려하여 정답이 같더라도 효율성과 구현 편의성에 따라 선택해야합니다.