DFS-> 한 길로 쭉 갔다가 막히면 되돌아가야함 


BFS-> 같은 층 전체를 한번에 훑고 지나감


좀 똑똑하면 여기서 알아채겠지 


'되돌아간다'


즉 되돌아간다는게 뭐냐 돌아가는 비용이 필요하다.


이걸 백트래킹 비용이라고 함


결국 방금 그문제는 되돌아가는 시간이 쌓여서 불필요한 이동 비용이 생김


DFS가 더 유리한 상황은 기본적으로


메모리 비용 절약, 완전탐색, 깊이 탐색인데


보통 깊이 탐색의 경우, 즉 얼리 리턴(조기 반환이라고 함)에는 DFS로 빠르게 Fail 치는게 나아서 그때가 더 나음


보통 N-Queen 문제라고 함. 이런 유형 문제는 DFS가 유리함


'최단거리' 이 글자 들어가면 무조건 BFS라고 이해하는게 낫다.