BFS/DFS) 1. 타겟 넘버

 

5개의 숫자 각각을 더하거나 빼서 타겟 넘버를 만드는 DFS 문제입니다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int cnt = 0;
int globalTarget = 0;

void dfs(const vector<int>& numbers, int idx, int totalSum)
{
    if (idx == numbers.size()) 
    {
        if (totalSum == globalTarget) 
        {
            cnt++;
        }
        return;
    }

    dfs(numbers, idx + 1, totalSum + numbers[idx]);
    dfs(numbers, idx + 1, totalSum - numbers[idx]);
}

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

int main()
{
    vector<int> v = { 1, 1, 1, 1, 1 };
    int target = 3;
    int res = solution(v, target);

    cout << res;
    return 0;
}

디버깅을 위해 VS 환경에서 작성을 했습니다.

 

    if (idx == numbers.size()) 
    {
        if (totalSum == globalTarget) 
        {
            cnt++;
        }
        return;
    }

기저 사례는 매 재귀마다 1씩 증가하는 idx가 numbers의 size와 같아질 때입니다.

왜냐하면 모든 수를 사용해서 계산하였을 때가 기준이기 때문입니다.

그 전에 target이 완성되더라도 나머지 수를 모두 사용해야 합니다.

 

dfs(numbers, idx + 1, totalSum + numbers[idx]);
dfs(numbers, idx + 1, totalSum - numbers[idx]);

두 줄이 실질적으로 로직을 이어나가는 부분입니다.

매 재귀마다 세 번째 인자로 number[idx]를 더하거나 빼서 필요한 경우의 수를 만들고,

두 번째 인자로 idx + 1을 넘겨줌으로써 굳이 for문을 사용하지 않게 했습니다.