문제

programmers43165

DFS/BFS로 주어진 숫자들을 적절히 덧셈/뺄셈해 타겟 넘버를 찾는 문제. stack, queue, 재귀를 사용해 세 가지 방법으로 풀었다.

stack을 이용해 DFS 구현

#include <string>
#include <vector>
#include <stack> // dfs
#include <utility> // pair
using namespace std;

int solution(vector<int> numbers, int target) {
    int answer = 0;
    stack< pair<int, int> > st;
    int size = numbers.size(); // (sum, cnt)
    
    st.push(make_pair(numbers[0], 1));
    st.push(make_pair(-numbers[0], 1));
    
    while(!st.empty()) {
        int sum = st.top().first;
        int cnt = st.top().second;
        st.pop();
        
        if(cnt >= size) {
            if(sum == target) answer++;
        }
        else {
            st.push(make_pair(sum + numbers[cnt], cnt+1));  
            st.push(make_pair(sum - numbers[cnt], cnt+1));            
        }
    }
    return answer;
}

재귀로 DFS 구현

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

int answer = 0;

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

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

queue를 이용해 BFS 구현

#include <string>
#include <vector>
#include <queue> // bfs
#include <utility> // pair
using namespace std;

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