DFS의 당위성 관련 질의

Question

안녕하세요 선생님! 강의를 잘 수강하고 있는 학생입니다. 저는 선생님 강의에서 DFS가 실제로 사용되는 것을 처음 배웠는데요! DFS의 개념도 알려주신 대로 잘 이해해보고 있습니다! 그런데 위 문제에 왜 DFS를 적용해야만 하는지 그 당위성에 대한 답변을 들을 수 있을까요? 예를 들어, 이 문제에서 요구하는 핵심은 이것이고, 이는 이러한 특징을 갖고 있다. 그래서 DFS를 써야만 한다, 하는 식으로요. 저는 이 문제에선 해당 숫자가 부분집합에 들어가느냐, 안들어가느냐 2가지 선택지가 핵심이므로 두 선택지가 주어지는 이진트리를 사용할 수 있다고 생각했고, 문제에서 전위 순회를 하라했으니 DFS 를 전위순회로 진행하면 되겠다고 유추했습니다! 보다 깊은 선생님의 이야기를 듣고싶습니다. 다음에 어떤 문제를 만났을 때, 그 문제를 해석해서 DFS와 연결시킬 수 있는 힘을 기르는 데 도움이 되지 않을까 하여 질의드립니다.

김태원 · Answer

안녕하세요^^ 글을 보니 지금 공부 잘 하고 있는 것 같습니다. 저도 별다른 내공없습니다. 문제를 많이 풀어본 경험에 의해서 DFS를 쓸건지, BFS를 쓸건지 판단합니다. 한 가지 기준이 있다면 모든 경우의 수를 일일히 확인해서 최상의 경우를 찾는 문제는 DFS를 쓰고, 최단거리를 구하거나 최소횟수를 구하는 문제는 BFS를 쓴다 정도의 감입니다. 그 이상의 감각적인 부분이 있지만 그것은 많은 문제를 풀어보는 경험을 통해서 얻는 힘이라 생각합니다.