프로그래머스 (타겟 넘버, 깊이/너비 우선 탐색(DFS/BFS)) C++

 

약간 음.... 이런 분위기의 문제가 있다. 딱 하나 정도 차이나는 +와 - / 인접한 주변의 것들을 비교하고 등등

이게 바로 dfs 재귀함수를 하라는 것이다. 카카오 컬러링북 문제랑 비슷하다. 느낌을 유지하자.

 

#include <string>
#include <vector>

using namespace std;

int answer = 0;

void recur(vector<int> numbers, int target, int sum, int count) {
    
    // count도 계속적으로 새서 count가 numbers 배열의 크기와 같아진 경우에
    // sum 또한 원하는 합 target과 동일하다면 answer를 증가시키고 return;으로 돌아간다.
    if(count == numbers.size()) {
        if(sum == target) answer++;
        return;
    }
    
    // 파라미터 중 하나로 넘어가는 것이 sum이다. 하나는 더하고 하나는 빼줘야 한다.
    // 즉 numbers의 인자가 5개이면 2의 5승 == 32개의 case를 전부 탐색하는 것.
    recur(numbers, target, sum+numbers[count], count+1);
    recur(numbers, target, sum-numbers[count], count+1);
}

int solution(vector<int> numbers, int target) {

    // 재귀함수를 호출한다.
    recur(numbers, target, 0, 0);
    return answer;
}