[programmers] Lv.2 타겟 넘버(c++)

DFS, BFS 두 방법으로 풀어봤다.

 

#include <vector>

using namespace std;

int answer=0;
void dfs(vector<int>& numbers, int& target, int idx, int num){
    if(idx+1 == numbers.size()+1){
        if(num == target) answer++;
        return;
    }
    dfs(numbers, target, idx+1, num+(-1)*numbers[idx]);
    dfs(numbers, target, idx+1, num+numbers[idx]);
}

void bfs(vector<int>& numbers, int& target){
    queue<pair<int, int>> que;
    que.push({numbers[0], 1});
    que.push({(-1)*numbers[0], 1});
    
    while(!que.empty()){
        auto [num, idx] = que.front(); que.pop();
        if(idx == numbers.size()){
            if(num == target) answer++;
            continue;
        }
        que.push({num + numbers[idx], idx+1});
        que.push({num + (-1)*numbers[idx], idx+1});
    }
}

int solution(vector<int> numbers, int target) {    
    dfs(numbers, target, 0, 0);
    // bfs(numbers, target);
    
    return answer;
}

---

문제

https://programmers.co.kr/learn/courses/30/lessons/43165

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

728x90

---

DFS

https://jolly-note.tistory.com/62?category=993245 

DFS (Depth First Search, 깊이 우선 탐색)

---

[접근1]

dfs 함수에 숫자가 담긴 벡터와, target number를 건내주고, numbers의 어느 숫자를 가르킬 지 나타내는 idx와 계산 숫자 num을 0으로 초기화하여 넣어준다.

dfs(numbers, target, 0, 0);

---

[접근2]

만약 numbers의 끝까지 돌았다면 함수를 더이상 dfs를 더 부르지 않고 끝내주는데,

만약 계산한 숫자가 target이랑 같으면 답을 1 증가시켜준다.

if(idx+1 == numbers.size()+1){
    if(num == target) answer++;
    return;
}

---

[접근3]

끝까지 돌지 않았다면, num에 다음 숫자를 더하거나 빼서 다음 dfs로 건내준다.

dfs(numbers, target, idx+1, num+(-1)*numbers[idx]);
dfs(numbers, target, idx+1, num+numbers[idx]);

---

BFS

https://jolly-note.tistory.com/63?category=993245 

BFS (Breadth First Search, 너비 우선 탐색)

---

[접근1]

queue에 처음숫자를 -1 곱한것과 곱하지 않은것 두가지를 넣고, idx는 다음 숫자를 가리키는것으로 넣어준다.

que.push({ numbers[0], 1 });
que.push({ (-1)*numbers[0], 1 });

---

[접근2]

queue가 빌때까지 반복하는데,

que의 맨 앞을 꺼내서 num과 idx에 넣는다.

만약 idx가 끝까지 돌았다면 while 조건문으로 돌아가는데 num이 target이랑 같으면 answer을 1 증가시켜준다. 

끝까지 돌지 않았다면, que에 현재 num에 다음 숫자를 더하거나 빼고 다음 idx를 가리키는 pair를 넣어준다.

while (!que.empty()) {
    auto[num, idx] = que.front(); que.pop();
    if (idx == numbers.size()) {
        if (num == target) answer++;
        continue;
    }
    que.push({ num + numbers[idx], idx + 1 });
    que.push({ num + (-1)*numbers[idx], idx + 1 });
}