[프로그래머스] 타겟 넘버 (DFS/BFS, C++)

💻 C++ 제출코드

---

#include <vector>
#include <string>

using namespace std;

int answer = 0;
void DFS(int sum, int index, int target, vector<int> *numbers){
    if(index == (*numbers).size()){ 
        if(sum == target) answer++;
        return;
    }
    DFS(sum + (*numbers)[index], index + 1, target, numbers);
    DFS(sum - (*numbers)[index], index + 1, target, numbers);
}

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

    DFS(0, 0, target, &numbers);
    return answer;
}

 

 

📝 문제풀이 과정

---

#include <stdio.h>
#include <vector>

using namespace std;
int answer = 0;
void DFS(int sum, int index, int target, vector<int> *numbers){
    if(index == (*numbers).size()){ 
        if(sum == target) answer++;
        return;
    }
    DFS(sum + (*numbers)[index], index + 1, target, numbers);
    DFS(sum - (*numbers)[index], index + 1, target, numbers);
}

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

    DFS(0, 0, target, &numbers);
    return answer;
}

int main(){
    vector<int> number;
    int n;

    scanf("%d", &n);

    for(int i=0; i<n; i++){
        int num;
        scanf("%d", &num);
        number.push_back(num);
    }
    int target;
    scanf("%d", &target);
    printf("# of target: %d\n", solution(number, target));
    
}

• index가 number.size()라는 것은 5개의 모든 원소를 sum에 더한 것이고, 이 결과를 target과 비교하여 같으면 answer을 1 증가시킨다.

 

 

🔍 DFS 노드 탐색 순서

---

DFS(0, 0)
{
      DFS(sum+num[0], 1)
      {
          DFS(sum+num[1], 2)
          {
              DFS(sum+num[2], 3)
              {
                  DFS(sum+num[3], 4)
                  {
                      DFS(sum+num[4], 5)
                      {
                          if(5 == num.size()) return;
                      }
                      DFS(sum-num[4], 5)
                      {
                          if(5 == num.size()) return;
                      }
                  }
                  DFS(sum-num[3]), 4)
                  {
                      DFS(sum+num[4]), 5)
                      {
                      }
                      DFS(sum-num[4]), 5)
                      {
                      }
                  }
  ...
...

• 재귀호출의 경우, 위와 같은 과정으로 함수를 호출하고 자신을 불렀던 함수로 리턴하는 과정을 반복한다. DFS(0,0)에서 마지막으로 DFS(sum-num[0], 1)을 끝내면 DFS(0,0)가 자신을 호출한 main 함수로 리턴하여 비로소 재귀를 끝낼 수 있게 된다.

[+1, +1, +1, +1, +1]
[+1, +1, +1, +1, -1]

[+1, +1, +1, -1, +1]
[+1, +1, +1, -1, -1]

[+1, +1, -1, +1, +1]
[+1, +1, -1, +1, -1]
[+1, +1, -1, -1, +1]
[+1, +1, -1, -1, -1]

[+1, -1, +1, +1, +1]
[+1, -1, +1, +1, -1]
[+1, -1, +1, -1, +1]
[+1, -1, +1, -1, -1]
[+1, -1, -1, +1, +1]
[+1, -1, -1, +1, -1]
[+1, -1, -1, -1, +1]
[+1, -1, -1, -1, -1]

[-1, +1, +1, +1, +1]
[-1, +1, +1, +1, -1]
[-1, +1, +1, -1, +1]
[-1, +1, +1, -1, -1]
[-1, +1, -1, +1, +1]
[-1, +1, -1, +1, -1]
[-1, +1, -1, -1, +1]
[-1, +1, -1, -1, -1]
[-1, +1, -1, -1, -1]
[-1, -1, +1, +1, +1]
[-1, -1, +1, +1, -1]
[-1, -1, +1, -1, +1]
[-1, -1, +1, -1, -1]
[-1, -1, -1, +1, +1]
[-1, -1, -1, +1, -1]
[-1, -1, -1, -1, +1]
[-1, -1, -1, -1, -1]

• 원소의 개수가 5개인 경우, 위와 같은 노드 탐색 순서를 갖는다.

 

 

👏 결과

---