[프로그래머스] 타겟 넘버 DFS C++

문제 :

https://programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

 

분석 :

재귀 방식을 이용해서 풀었다. DFS/ BFS는 재귀 or stack + visit 판별 방식으로 풀 수 있는데 이번 문제는 재귀가 더 직관적일 것 것 같아서 재귀 방식으로 접근했다. 중요한 것은 재귀 종료 조건이다. 총 원소의 숫자만큼 depth를 내려갔다면 빠져나온다.

처음엔 -로 dfs를 돌때 depth를 왜 증가시켜주나 의문이었는데 위 재귀에서 return 시 자신의 루트 노드로 돌아오기 때문에 마찬가지로 depth + 1 해주어야 한다.

 

핑크색 글씨는 방문 순서다 !!

 

c++ 코드 :

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

using namespace std;
int cnt = 0;

void dfs(vector<int> numbers, int target, int sum, int depth){

    if(depth == numbers.size()){ // 종료 조건
        if(sum == target){
            cnt++;
        }
        return;
    }else {
        dfs(numbers, target, sum + numbers[depth], depth+1);
        dfs(numbers, target, sum - numbers[depth], depth+1);
    }
    
    
}

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

 

결과 :