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

타겟 넘버

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

풀이 방법

백트래킹과 유사한 느낌으로 BFS를 사용해서 문제를 해결했다. 문제에서 주어진 예시만 얼핏 봐도 백트래킹이라고 생각할 수 있다.

어쨌든 나는 BFS를 이용해서 풀이했는데, BFS를 위해 사용될 Queue에는 아래 네 가지 정보가 들어가게 된다.

1. 해당 index
2. 음양 부호
3. 현재 숫자의 합
4. 남은 숫자의 합

큰 틀은 Queue에 정보들을 넣으며 너비 우선 탐색을 진행하면서 index와 음양 부호를 통해 현재 합과 남은 숫자의 합을 구해 가지치기를 할 것인지 정답을 셀 것인지 다음 수를 진행할 것인지 결정하는 것이다.

현재 숫자의 합인 cur은 타겟 넘버와의 부등호 조건식을 통해 정답을 세어줄지 그냥 넘길 것인지 결정한다.

코드에도 나와있지만 cur이 타겟 넘버보다 작을 때, 사용한 숫자를 제외한 나머지 숫자인 sum을 더해도 타겟 넘버보다 작다면 더 이상 진행할 필요가 없으므로 continue 문장을 실행한다.

반대로 cur이 타겟 넘버보다 크거나 같을 때, 사용한 숫자를 제외한 나머지 숫자를 빼도 타겟 넘버보다 크다면 더 이상 진행할 필요가 없으므로 continue 문장을 실행한다.

사실 위의 가지치기 논리는 효율성을 최대한 높이려고 짠 거긴 하지만 이 문제에서는 숫자의 개수가 최대 20개여서 필요 없을 것 같긴 하다.

소스 코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

int solution(vector<int> numbers, int target) {
    int answer = 0, num_sum = 0;

    for(auto i : numbers)
        num_sum += i;

    queue<tuple<int, int, int, int>> q;

    q.push({0, 1, 0, num_sum});
    q.push({0, -1, 0, num_sum});

    while(!q.empty()) {
        int idx = get<0>(q.front());
        int pm = get<1>(q.front());
        int cur = get<2>(q.front()) + numbers[idx] * pm;
        int sum = get<3>(q.front()) - numbers[idx];
        q.pop();

        if(cur == target && idx == numbers.size() - 1) {
            answer++;
            continue;
        }
        else if(idx + 1 >= numbers.size())
            continue;

        if(cur < target)
            if(cur + sum < target)
                continue;
        else
            if(cur - sum > target)
                continue;

        q.push({idx + 1, pm, cur, sum});
        q.push({idx + 1, -pm, cur, sum});
    }

    return answer;
}