BFS vs DFS

알고리즘에서 BFS와 DFS 중에 어떤거를 적용할지 헷갈릴때가 많다.

정리하는 

 

DFS를 사용하는 경우

1.  특정 지점에서 출발해 목적지까지가는 모든 경로를 탐색하는 경우

   ex) 미로찾기, 퍼즐문제

2. 순열/조합 생성하는 문제

   ex) 주어진 숫자로 가능한 모든 숫자 조합 만들기

3. 재귀적으로 문제를 해결할때

   ex)백트래킹 문제

 

 

BFS를 사용하는 경우 

1. 최단 경로를 찾는 문제

   ex) 미로에서 최단거리 찾기, 특정 도시간 최단 경로 탐색

2. 최소 비용 문제

   ex) 체스판의 나이트 이동 최소 획수

3. Flood fill 문제

   ex) 그림판에서 색을 채우는 문제, 섬의 개수 찾기 

 

한눈에 이해하기

• DFS: "한 가지 길을 끝까지 파고들고 싶다!"
• BFS: "모든 길을 동시에 살펴보며 가장 빠른 길을 찾고 싶다!"