Programmers / 타겟 넘버 / C++

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 타겟 넘버 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 
문제 설명
 

---

 
나의 풀이
 

#include <string>
#include <vector>

using namespace std;

int result = 0;

void bfs(int target, vector<int> &numbers, int idx, int sum) {
    if (idx == numbers.size()) {
        if (sum == target) {
            result++;
        }
        return;
    }

    bfs(target, numbers, idx + 1, sum + numbers[idx]);
    bfs(target, numbers, idx + 1, sum - numbers[idx]);

}

int solution(vector<int> numbers, int target) {
    bfs(target, numbers, 0, 0);

    return result;
}

 
입출력 예 #2를 그림으로 표현해봤다. 위와 같은 그림의 형태가 나오게 된다. 중간에 if문에서 return를 하는 코드가 있는데 그건 idx가 numbers.size()와 같아지면 dfs를 더 이상 실행할 필요가 없어서 종료하기 위해 만들었다.
 

---

※ 알아야 할 것

 
너비 우선 탐색(BFS)은 특정 정점에서 시작하여 인접하는 정점을 방문해 나가면서 탐색을 하는 탐색을 말한다.