PGMRS : 타겟 넘버 - 순열, DFS, BFS [3가지 풀이]

순열 풀이

#include <iostream>
#include <vector>
using namespace std;
int cnt;
void Fast_IO() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    return;
}
void Cal_to_target(const vector<int>& numbers, int tg, int idx, int currentSum, int& cnt) {
    if (idx == numbers.size()) {
        if (currentSum == tg) cnt++;
    } else {
        Cal_to_target(numbers, tg, idx + 1, currentSum + numbers[idx], cnt);
        Cal_to_target(numbers, tg, idx + 1, currentSum - numbers[idx], cnt);
    }
    return;
}
int solution(vector<int> numbers, int target) {
    Fast_IO();
    Cal_to_target(numbers, target, 0, 0, cnt);
    answer = cnt;
    return answer;
}

• 숫자 앞에는 부호 + 혹은 -가 온다. 이를 경우의 수로 나열하면 2^(숫자의 수, 즉, 벡터의 사이즈) 가 된다. 최대 벡터의 크기는 20이므로 최대 시간 복잡도는 2^20이 된다. 이는 1,048,576 이라는 수로 계산하기 부담되는 수는 아니다.
• 주요 함수인 Cal_to_target()을 보자.

void Cal_to_target(const vector<int>& numbers, int tg, int idx, int currentSum, int& cnt) {
    if (idx == numbers.size()) {
        if (currentSum == tg) cnt++;
    } else {
        Cal_to_target(numbers, tg, idx + 1, currentSum + numbers[idx], cnt);
        Cal_to_target(numbers, tg, idx + 1, currentSum - numbers[idx], cnt);
    }
    return;
}

• 
• idx가 numbers.size()와 같아야 계산이 끝났음을 알 수 있고, 이에 따라 target과 비교가 가능하다. 기존에는 -1을 해버려서 계산이 온전히 끝나지 않았었다.
• 그게 아니면, idx는 1씩 더해지고, currentSum(지금까지의 계산 값)에 numbers[idx]로 더하거나 뺌을 재귀적으로 반복하는 구조를 가진다.
• numbers[idx]를 함으로써, 이전까지의 합(currentSum)과 현재 요소의 합 혹은 뺄셈(numbers[idx])을 수행한다. 이를 단순하게 식으로 넣지 않고, 매개변수로 바로 넣으면서 currentSum = currentSum +- numbers[idx]의 구조로 반복 호출이 되는 것이다.

// BFS 해답
#include <iostream>
#include <vector>
#include <queue>
#include <utility> // make_pair() 사용
using namespace std;
int answer;

void Fast_IO() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    return;
}
// BFS 해답
void BFS(vector<int> num, int tgt){
    queue<pair<int,int>> q1;	     // 큐 선언 
    q1.push(make_pair(0, num[0]));   // 큐 푸시 (+ 버전)
    q1.push(make_pair(0, -num[0]));  // 큐 푸시 (- 버전)
    while(!q1.empty()){				 // BFS의 while()
        int idx = q1.front().first;  	// idx = Index
        int res = q1.front().second; 	// res = Index에 위치한 값
        q1.pop(); 
        // cout << "idx: " << idx << " res: " << res << " q size: " << q1.size() << '\n';
        if(idx == num.size() - 1 && res == tgt){
            answer += 1;
        }
        if(idx + 1 < num.size()){
            q1.push(make_pair(idx + 1, res + num[idx + 1]));
            q1.push(make_pair(idx + 1, res - num[idx + 1]));
        }
    }
    return;
}

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

• 알고 있던 BFS를 그대로 쓰셨다.
• 큐 선언 -> pair를 만들어서 (0, +num[0]) (0, -num[0]) 삽입 -> while 내에서 idx, res에 각각 저장하고, pop으로 빼내기 -> idx가 벡터 마지막 요소 위치이고 현재까지 계산값 res가 타겟과 같으면 경우의 수 1 증가
• 그리고, 마지막 요소 도달할 때까지 idx+1과 + 혹은 -한 num[idx+1] 넣기
• 위의 순열 버전 코드와 다른 점은 num[idx+1]로 넣는다는 점

// DFS 해답
#include <iostream>
#include <vector>
using namespace std;
int answer;
void DFS(vector<int> &numbers, int &target, int sum, int idx) {
    if(n >= numbers.size()){
        if(sum == target) answer++;
        return;
    }
    DFS(numbers, target, sum + numbers[idx], idx+1);
    DFS(numbers, target, sum - numbers[idx], idx+1);
}
int solution(vector<int> numbers, int target) {
    int answer = 0;
    DFS(numbers, target, numbers[0] , 1);
    DFS(numbers, target, -numbers[0], 1);
    return answer;
}

• 위의 두 코드를 보고 나니 더 이해하기 편하군. 이정도면 간단한 형태의 재귀 문제라고 생각한다.
• 재귀 문제 부숴보자. 이 문제도 위의 두 코드와 마찬가지로 현재까지의 합 + 벡터의 + 혹은 - 형태 값을 누적해서 저장하는 형태로 idx+1을 넘긴다.