[Programmers_C++]#Level2_타겟 넘버, DFS, 재귀 호출

 

#1. 문제

 

 

 

---

 

#2. 풀이

 

1. DFS

[자료구조]#6_그래프

 

• [정의] : DFS(깊이 우선 탐색)은 그래프 내 모든 정점을 탐색하는 방법 중 하나입니다.
• [특징] : DFS는 현재 정점을 기준으로 깊은 탐색을 우선적으로 진행하고, 다음 인접 정점에 대한 깊이 탐색을 진행.
• [구현]
  1. 재귀 호출
  2. 스택

 

2. 두 개의 DFS - 양수에 대한 재귀 DFS, 음수에 대한 재귀 DFS

1. numbers 목록의 첫 번째 정점을 시작으로 양수 값에 대한 DFS와 음수 값에 대한 DFS를 호출합니다.
2. DFS는 인자 목록 중 'plusOrMinus'를 전달받아, sum 계산에 sum += plusOrMinus * numbers [curIdx] 합니다.
3. [조건] : DFS는 sum이 target이 같을 경우, DFS를 종료하고 answer에 +1을 더해줍니다.
4. 조건을 만족하지 못했을 경우, 다시, 양수 값에 대한 DFS와 음수 값에 대한 DFS를 재귀적으로 수행합니다.

 

---

 

#3. 코드

 

#include <string>
#include <vector>

using namespace std;

// /#1. DFS 정의, 다음 Index에 대해 두 개의 DFS를 재귀적으로 수행
void DFS(int &answer, int plusOrMinus, int curIdx, const int &target, int sum, vector<int> &numbers)
{
    sum += (plusOrMinus * numbers[curIdx]);
    if (curIdx == numbers.size() - 1)
    {
        if (sum == target)
        {
            answer++;
        }
        return;
    }

    DFS(answer, 1, curIdx + 1, target, sum, numbers);
    DFS(answer, -1, curIdx + 1, target, sum, numbers);
}

int solution(vector<int> numbers, int target)
{
    int answer = 0;
    int sum = 0;

    // #1. 양수 버전의 DFS 수행
    DFS(answer, 1, 0, target, sum, numbers);
    // #2. 음수 버전의 DFS 수행
    DFS(answer, -1, 0, target, sum, numbers);

    return answer;
}

 

---