08_01 합이 같은 부분 집합

Question

왜 dfs로 풀어야하는지 잘 이해가 되지않습니다. 집합의 일부분을 사용하고 value의 값이 가장 먼저 나오는 node를 찾으면 되는 문제로 판단하고 bfs로 제출했더니 런타임오류가 발생했습니다. 아직 개념이해가 부족해 잘못된 접근 방식인건지 잘모르겠습니다. 관련해서 설명부탁드겠습니다.

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. DFS(깊이 우선 탐색)를 사용하여 문제를 풀어야 하는 이유는, 합이 같은 부분 집합 문제에서는 모든 부분 집합을 고려하여 탐색해야 하기 때문입니다. 이 문제는 주어진 집합의 모든 부분 집합 중에서 그 합이 특정 값과 같은 경우를 찾아야 하는데, 이를 위해서는 부분 집합을 체계적으로 생성하면서 탐색해야 합니다. DFS를 사용하면 현재 원소를 포함하는 경우와 포함하지 않는 경우로 나누어 모든 부분 집합을 생성하면서 합을 계산해볼 수 있습니다. 이 과정에서 합이 같은 부분 집합을 효율적으로 찾아낼 수 있습니다. 반면에 BFS(너비 우선 탐색)는 각 노드에서 가능한 모든 자식 노드를 동시에 탐색하는 방식으로, 이 문제에 적용했을 때 메모리 사용량이 많아지고, 모든 부분 집합을 생성하는데 있어서 BFS보다는 DFS가 더 적합합니다. 특히 합이 같은 부분 집합을 찾는 문제는 결정해야 하는 선택지(현재 원소를 포함할지 여부)가 많아질수록 탐색해야 하는 경우의 수가 기하급수적으로 늘어나게 됩니다. DFS는 이런 경우 선택지 하나하나에 대해 깊게 파고들면서 해답을 도출해낼 수 있는 반면, BFS는 모든 가능성을 넓게 탐색하기 때문에 이런 종류의 문제에서는 더 불리할 수 있습니다. 따라서, 합이 같은 부분 집합 문제에서 DFS를 사용하면 효율적으로 모든 경우의 수를 탐색하면서 해결 방법을 찾을 수 있게 됩니다. 실행 중인 런타임 오류는 BFS를 활용한 접근 방식에서 발생하는 것일 수 있으며, DFS로 문제를 접근하면서 오류를 해결해 볼 수 있을 것입니다.