프로그래머스(깊이/너비 우선탐색; 타겟 넘버) c++

#include <string>
#include <vector>

using namespace std;

int answer = 0;


void dfs(vector<int>& numbers, int target, int idx, int sum)
{
    // 하나의 경로가 도달했을때 목표치에 도달했는지 검사 후 종료
    if(idx == 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) 
{
    dfs(numbers, target, 0, 0);
    return answer;
}

 

해설:

 

numbers에서 target으로 향하는 모든 경우의 수를 찾기 위해서 dfs를 이용하여 전체 탐색하여 경우의 수를 모두 탐색한다.

 

첫번째: 정의한 dfs 함수에 number와 목표인 target, 현재 인덱스(idx), 합계(sum+numbers[idx], sum-numbers[idx] 두가지 경우 분기를 만들 수 있다)를 받는다.

두번째: 모든 경로가야하면서도 음수, 양수대한 분기도 해야하기에 sum + numbers[idx], sum - number[idx] 를 통해 첫 인덱스부터 분기를 만들 수 있다.

세번째: 그렇게 하나의 경로가 idx == number.size()와 같이 도달했을때 해당 경로가 target 목표치와 sum이 동일할때 경우의 수를 증가 시킨다.