[프로그래머스 43165] 타겟 넘버

• 출처: 프로그래머스 43165
• 분류: DFS/BFS · Lv.2

문제

음이 아닌 정수 배열 numbers와 정수 target이 주어진다. 각 수를 순서대로 더하거나 빼서 합이 target이 되는 경우의 수를 반환한다.

핵심

각 수마다 +/− 두 갈래로 분기하는 이진 트리 탐색이다. 리프에서 합이 target과 같으면 카운트한다.

플로우차트

dfs(idx, sum)
  │
  ├─ idx == n?
  │    ├─ Yes → sum == target? → Yes → count++
  │    │                        → No  → return
  │    └─ No  → dfs(idx+1, sum + nums[idx])
  │           → dfs(idx+1, sum - nums[idx])

풀이

#include <vector>
using namespace std;

int answer = 0;

void dfs(const vector<int>& numbers, int target, int idx, int sum) {
    if (idx == (int)numbers.size()) {
        if (sum == target) answer++;
        return;
    }
    dfs(numbers, target, idx + 1, sum + numbers[idx]);
    dfs(numbers, target, idx + 1, sum - numbers[idx]);
}

int solution(vector<int> numbers, int target) {
    answer = 0;
    dfs(numbers, target, 0, 0);
    return answer;
}

메모

• 각 수에 대해 2가지 선택이 있으므로 총 탐색 수는 2^N이다. N ≤ 20이므로 최대 약 100만으로 충분하다
• visited 배열이 필요 없다. 순서가 고정된 단방향 탐색이라 같은 노드를 재방문하지 않는다
• 전역 변수 answer를 쓰는 대신 반환값으로 카운트를 전달하는 방법도 있다:

int dfs(const vector<int>& numbers, int target, int idx, int sum) {
    if (idx == (int)numbers.size())
        return sum == target ? 1 : 0;
    return dfs(numbers, target, idx + 1, sum + numbers[idx])
         + dfs(numbers, target, idx + 1, sum - numbers[idx]);
}

int solution(vector<int> numbers, int target) {
    return dfs(numbers, target, 0, 0);
}

• BFS로도 풀 수 있다. 큐에 {idx, sum}을 넣고 레벨별로 확장하면 된다. 이 문제에서는 DFS가 코드가 짧다

복잡도

풀이	시간	공간
DFS	O(2^N)	O(N) 재귀 스택
BFS	O(2^N)	O(2^N) 큐