깊이/너비 우선 탐색(DFS/BFS) / 타겟 넘버 / C++

문제 설명

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

 

제한 사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

입출력 예

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

---

 

문제 이해

---

처음부터 끝자리 수까지 더해야 한다.

각 자리마다 음수 혹은 양수로 될 수 있다.

이 두 조건을 일일이 나열해 보면 아래와 같이 확장이 된다.

여기서 하나의 일관된 규칙이 있는데, 바로 현재수 + 다음 index의 +정수, -정수이다. 

 

알고리즘 정리

위에서 이해한 내용을 의사코드로 표현하면 다음과 같이 DFS로 탐색을 하고,

//DFS 의사코드
DFS(0,0)
  DFS(다음 수, 누적합산 + 현재수)
  DFS(다음 수, 누적합산 - 현재수)

추가로 마지막 수까지 더하면 또다시 재귀로 DFS를 호출하지 않도록 target 값과 그간 누적 값이 같은지 비교해서 같으면 경우의 수를 +1 하고 그렇지 않으면 종료하는 예외처리도 추가한다.

 

코드

• 코드 실행해 보기 (아래 우측 상단 아이콘 선택 시 실행 가능)

 

같은 내용을 BFS로 탐색을 하여 탐색 기법의 장단점을 더욱 이해해 봐야겠다.

BFS 로 문제 해결

BFS 로 해결하기 좋은 문제는 아닌 것 같지만 공부해보는 차원에서 너비 우선 탐색으로 진행해보고자 한다.

우선 하나 하나의 케이스를 정리해보면
idx 0 (첫 번째 숫자)
sum[0] = sum[0] + number[inx]
sum[0] - sum[1] + number[inx]

idx 1(두 번째 숫자)
temp_sum = sum; // sum 과 temp_sum 인자 필요
sum[0] = temp_sum[0] + number[inx+1]
sum[0] = temp_sum[0] - number[inx+1]

sum[1] = temp_sum[1] + number[inx+1]
sum[1] = temp_sum[1] - number[inx+1]

모든 덧셈/뺄셈의 케이스의 결과 값을 가지고 있어야 하기에 sum 은 경우의 수 만큼의 size 필요
다음 덧셈/뺄셈에 이전에 합산한 결과(sum)가 필요하기에 temp_sum는 sum 의 절반 사이즈 만큼 필요하다. 
(다음 덧셈/뺄셈은 전 case 의 2배수로 증가)

idx 2(두 번째 숫자)
temp_sum = sum;
sum[0] = temp_sum[0] + number[inx+1]
sum[1] = temp_sum[0] - number[inx+1]

sum[2] = temp_sum[1] + number[inx+1]
sum[3] = temp_sum[1] - number[inx+1]

sum[4] = temp_sum[2] + number[inx+1]
sum[5] = temp_sum[2] - number[inx+1]

sum[6] = temp_sum[3] + number[inx+1]
sum[7] = temp_sum[3] - number[inx+1]

(두번째 숫자)부터는 아래와 같이 일관된 로직을 만들 수 있다.
for(int numInx = 0; numInx<= number.size(); numInx++)
    temp_sum = sum;
    sumcounter =0;
    recurse = pow (2, numInx) //매 case 마다 2배의 연산 case 가 생긴다.
    for(int i = 0 ; i<= recurse ; i++)
        sum[sumcounter++] = temp_sum[i] + number[numInx+1]
        sum[sumcounter++] = temp_sum[i] - number[numInx+1]

 

코드

• 전체코드

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
 
using namespace std;
 
vector<int> gNumbers;
int numbers_size;
int g_target;
int answer;
 
void BFS() {
    vector<int> temp_sum, sum;
    int sum_counter = 0;
    double sum_result_size = pow(2, numbers_size);
    temp_sum.resize(sum_result_size, 0);
    sum.resize(sum_result_size, 0);
 
    //idx 0
    sum[sum_counter++] = + gNumbers[0];
    sum[sum_counter++] = - gNumbers[0];
 
 
    //idx 1~ numbers size
    for (int numInx = 1; numInx < numbers_size; numInx++) {
        temp_sum = sum;
        sum_counter = 0;
        double recurse = pow(2, numInx);
        for (int i = 0; i < recurse ; i++) {
            sum[sum_counter++] = temp_sum[i] + gNumbers[numInx];
            sum[sum_counter++] = temp_sum[i] - gNumbers[numInx];
        }
        cout << "sum_counter : " << sum_counter << " numInx : " << numInx << endl;
    }
 
    for (int numInx = 0; numInx < sum_result_size; numInx++) {
        if (g_target == sum[numInx]) {
            answer++;
        }
    }
    return;
}
 
int solution(vector<int> numbers, int target) {
    answer = 0;
    gNumbers = numbers;
    g_target = target;
    numbers_size = numbers.size();
    BFS();
 
    return answer;
}
 
int main()
{
    vector<int> numbers = {1, 1, 1, 1, 1};
    cout << solution(numbers,3);
}

• 코드 실행해 보기 (아래 우측 상단 아이콘 선택 시 실행 가능)

 

참고

---

DFS/BFS 개념 참고 사이트 :

https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/