[프로그래머스] 타겟 넘버 | C++ | DFS BFS (bfs 이해 필요)

 코딩테스트 연습 - 타겟 넘버 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

문제 설명

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 이하인 자연수입니다.

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

입출력 예 설명

입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

 

풀이

[1, 1, 1, 1, 1]
각 숫자는 +부호가 붙거나 -부호가 붙을 수 있다.

DFS

+와 - 부호로 각각 dfs 수행

BFS

소스

1) dfs 풀이

#include <string>
#include <vector>
#include <iostream>
using namespace std;

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

int solution(vector<int> numbers, int target) {
    int answer = 0;
    
    dfs(0, 0, numbers, target);    
    answer = ans;
    cout << answer << "\n";
    
    return answer;
}

 

2) bfs 풀이

#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

int bfs(vector<int> numbers, int target) 
{
    queue<pair<int, int>> q;
    int answer = 0;
    int sum = 0;
    int idx = 0;
    
    q.push({numbers[0], 0});
    q.push({-numbers[0], 0});
        
    while (!q.empty()) {
        pair<int, int> data;
        data = q.front();
        sum = data.first;
        idx = data.second;    
        q.pop();
        
        if (data.second == numbers.size() - 1){
            if (sum == target)
                answer++;
        }
        else {
            q.push({sum + numbers[idx+1], idx + 1});     
            q.push({sum - numbers[idx+1], idx + 1});    
        }        
    }    
    return answer;
}

int solution(vector<int> numbers, int target) {
    int answer = 0;
    
    answer = bfs(numbers, target);    
    //cout << answer << "\n";
    
    return answer;
}