✨ DFS

• 깊이 우선 탐색

• 호출되는 함수의 구조를 트리로 보면, 매 호출마다 트리의 높이가 증가

• BFS와 다르게 리턴 동작이 존재(이전 높이로 돌아온다)

• 시간복잡도는 O(V + E), 모든 V를 방문해서 총 E번만큼 움직이므로

✨ BFS

• 너비 우선 탐색

• 호출되는 함수의 구조가 트리라면, 같은 높이의 함수들이 호출된다

• 시간복잡도는 O(V + E), 모든 V를 방문해서 총 E번만큼 움직이므로

✨ DFS vs BFS

• DFS는 어떤 높이의 함수가 리턴될 때, 이전 높이의 함수로 돌아간다는 사실이 중요

• BFS는 같은 높이의 함수들을 모두 실행하므로, 이전 높이의 함수로 돌아가지 못함

✨ 언제 DFS를 써야할까?

• 방문되어진 경로에 따라서 조건이 바뀔 때(비트마스크)

• 명확한 종료 시점이 존재할 때

✨ 언제 BFS를 써야할까?

• 종료 시점이 불분명하지만, 정답은 존재할 때