프로그래머스 타켓 넘버

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

프로그래머스

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

• 1+1+1+1+1 = 3
• +1-1+1+1+1 = 3
• +1+1-1+1+1 = 3
• +1+1+1-1+1 = 3
• +1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

---

DFS/BFS

너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)는 그래프나 트리와 같은 자료구조를 탐색하는 데 사용되는 알고리즘이다. 주어진 문제를 해결하기 위해서는 이러한 알고리즘들이 어떻게 동작하는지 먼저 이해해야 한다.

 

너비 우선 탐색(BFS)

1. 큐(Queue) 사용: BFS는 큐를 사용하여 구현된다. 큐는 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out) 구조를 가지고 있다.
2. 인접한 노드들 탐색: 탐색을 시작할 노드를 큐에 넣고, 그 노드와 인접한 노드들을 모두 큐에 넣는다.
3. 레벨별 탐색: 먼저 들어온 노드를 먼저 처리하기 때문에 한 레벨의 모든 노드를 탐색한 후, 그 다음 레벨로 넘어간다.
4. 반복 수행: 큐가 빌 때까지 반복하여 탐색을 계속한다.

 

깊이 우선 탐색(DFS)

1. 스택(Stack) 사용: DFS는 스택을 사용하여 구현된다. 스택은 나중에 들어온 데이터가 먼저 나가는 LIFO(Last In First Out) 구조를 가지고 있다.
2. 한 경로 탐색: 시작 노드부터 한 경로를 끝까지 탐색한다.
3. 재귀 호출 또는 명시적 스택: DFS는 주로 재귀 호출을 사용하여 구현되지만, 명시적 스택을 사용하여 반복적으로 구현할 수도 있다.
4. 한 경로의 모든 노드 탐색: 한 경로의 끝까지 탐색하고, 그 다음 경로로 넘어간다.

이 문제는 모든 가능한 방법의 수를 찾아야 하므로 DFS가 더 적합하다. 하지만 BFS를 사용하여도 문제를 해결할 수 있다.

 

알고리즘

1. 시작 노드를 스택에 넣는다. (타겟 넘버와 현재 합을 함께 저장)
2. 스택에서 노드를 하나씩 꺼내며, 가능한 모든 경우를 탐색한다.
3. 한 경로의 모든 노드를 탐색한 후에는 다시 이전 노드로 돌아간다.
4. 모든 경로를 탐색할 때까지 반복하여 모든 가능한 경우를 찾는다.

 

코드

#include <string>
#include <vector>

using namespace std;

int dfs(vector<int>&numbers,int target,int idx, int total){
    if(idx==numbers.size()){
        if(total==target)
            return 1;
        else
            return 0;
    }
    
    int cnt=0;
    cnt+=dfs(numbers,target,idx+1,total+numbers[idx]);
    cnt+=dfs(numbers,target,idx+1,total-numbers[idx]);
    return cnt;
}

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

cnt+=dfs(numbers,target,idx+1,total+numbers[idx]);
cnt+=dfs(numbers,target,idx+1,total-numbers[idx]);
return cnt;

주어진 코드 블록에서 dfs 함수가 두 번 호출되고, 그 결과가 **cnt**에 더해진다.

첫 번째 호출은 **total**에 현재 인덱스의 숫자를 더한 경우를 나타낸다. 두 번째 호출은 **total**에서 현재 인덱스의 숫자를 뺀 경우를 나타낸다.

이렇게 두 가지 경우가 모두 고려되어야 하며, 이 두 경우의 결과가 모두 **cnt**에 더해져야 한다.

따라서 위 코드 블록은 한 번의 dfs 호출로 두 가지 서로 다른 경우를 고려한다.

즉, 한 번은 현재 숫자를 더한 경우를 탐색하고, 다른 한 번은 현재 숫자를 뺀 경우를 탐색한다. 이렇게 두 가지 경우를 동시에 탐색하면서 재귀적으로 모든 가능한 경우를 찾게 된다.

따라서 이 방식은 현재 숫자를 더하거나 빼는 두 가지 방법을 모두 고려하여 타겟 넘버를 만드는 모든 가능한 경로를 탐색하는 방식이다.

예시로 [1, 2, 3] 배열과 타겟 넘버를 3으로 가정하고, 그림으로 나타내면 다음과 같다.

              dfs(0, 0)
            /          \\
   dfs(1, 1)            dfs(1, -1)
     /   \\                  /   \\
dfs(2, 3)  dfs(2, -1) dfs(2, 1) dfs(2, -3)
   /  \\        /   \\       /   \\
dfs(3, 6) dfs(3, 2) ...  ...   ...

위 그래프에서 노드는 dfs 함수 호출을 나타낸다. 각 노드의 값은 함수 호출에 전달되는 매개변수를 나타낸다. 예를 들어, **dfs(1, 1)**은 dfs 함수가 첫 번째 숫자를 더한 상태에서 다음 숫자로 진행되는 호출을 나타낸다.

이 그래프에서 두 가지 중요한 점을 알 수 있다:

1. 각 노드는 현재까지의 합(total)과 다음에 사용할 숫자의 인덱스(idx)를 나타낸다.
2. 재귀 호출을 통해 그래프를 계속 확장하고, 가능한 모든 경로를 탐색한다.