[프로그래머스 43165] 타겟 넘버 C++

문제

프래그로머스 43165 타겟 넘버 C++

코딩테스트 연습 - 타겟 넘버

풀이

BFS를 사용했습니다.

첫 숫자의 음수 값, 양수 값을 queue에 push 해주고

queue에서 하나씩 꺼내며 양수를 더한 값, 음수를 더한 값을 다시 queue에 push 합니다.

소스 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 숫자, cnt
queue<pair<int, int>> q;
int solution(vector<int> numbers, int target) {
    int answer = 0;
    int Size = numbers.size();
    // 첫 숫자 push
    q.push(make_pair(numbers[0], 1));
    q.push(make_pair(-numbers[0], 1));
    // 두번째 숫자부터
    while (!q.empty()) {
        int num = q.front().first;
        int cnt = q.front().second;
        q.pop();
        // 끝까지 왔고, 타겟 넘버랑 같으면 answer++
        if (cnt == Size) {
            if (num == target) {
                answer++;
            }
        }
        // 끝이 아닌 경우에는 현재 숫자와 numbers의 숫자의 합, 차를 push
        else {
            q.push(make_pair(num + numbers[cnt], cnt + 1));
            q.push(make_pair(num - numbers[cnt], cnt + 1));
        }
    }
    return answer;
}