• DFS( 깊이 우선 탐색 ) : 하나의 드라마 끝까지 정주행
• BFS( 너비 우선 탐색 ) : 각각의 드라마를 한편씩 정주행
• 대표적인 문제 유형
  • 경로 탐색 유형 ( 최단 거리, 시간 )
  • 네트워크 유형 ( 연결 )
  • 조합 유형 ( 모든 조합 만들기 )

DFS ( 깊이 우선 탐색 )

BFS ( 너비 우선 탐색 )

• 둘 다 탐색을 하는 알고리즘으로 어떤 것을 사용 하더라도 정답은 나온다.
• 단, DFS 가 검증이 수월하다. DFS 는 하나의 조합을 완성해서 정답과 비교하고 또 다른 조합을 만들어 보고 정답과 비교하는 식으로 동작하기 때문에 정답을 비교하는 시점에 내가 기대한 대로 조합이 잘 나왔는지를 확인하기가 빠르고 쉽습니다.
• 그에 비해 BFS 는 한 번에 여러 조합들을 한칸 한칸씩 만들다 보니, 조합이 완성되어서 정답과 비교하는 시점에 언제 어떻게 이렇게 만들어졌는지 추적이 어렵습니다.
• 그렇다면 DFS 만 쓰면 되는 건가? 그건 아니다. 알고리즘에서는 짧은 시간에 검증을 해야하는 것인데 DFS 는 한 놈만 패는 과정이 너무 오래 걸린다면 시간이 초과 될 수 있습니다.
• 즉, DFS 는 수행 시간 관점에서는 복불복 운이 좋으면 첫 번째 조합이 최적의 답 운이 나쁘면 모든 조합을 다 만들어보면서 시간을 낭비
• BFS 는 모든 경우의 수를 한 걸음씩 나가기 때문에 초반에는 느려보일 수 있지만 하나의 정답만 찾고나면 나머지 경우의 수는 정답에서 제외 됩니다. 대박날 확률도 낮지만, 쪽박찰 확률도 낮다 == 시간복잡도가 낮다

문제 연습