[Programmers] 깊이/너비 우선 탐색(DFS/BFS) > 타겟 넘버(c++)

 

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

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

 

문제에 대해 감이 잘 잡히지 않아서 구글 검색으로 솔루션을 찾아 각각 DFS와 BFS로 구현했다.

DFS는 재귀로, 인덱스 1부터 numbers.size()까지 노드를 다 탐색했을 경우, sum값과 target값을 비교해 같을때 answer값을 1씩 증가시켰다.

 

DFS

 

 

DFS 코드 c++

void dfs(vector<int> numbers, int target, int sum, int i){
    if( i == numbers.size()){
        if(sum == target) answer++;
        return;
    }
    dfs(numbers, target, (sum - numbers[i] ), i+1);
    dfs(numbers, target, (sum + numbers[i] ), i+1);
}

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

 

 

 

 

---

BFS는 큐로 구현했고, 상위 큐 사이즈를 기준으로 push, pop을 반복하며 마지막 리프노드만 남았을 때, target과 값이 같은 리프노드의 개수만큼 answer++ 해줬다.

 

 

BFS

 

 

BFS 코드 c++

int answer = 0;
void bfs(vector<int> numbers, int target){
    queue<int> q;
    q.push(-numbers[0]);
    q.push(numbers[0]);
    
    for(int i=1;i<numbers.size();i++){
        int node_count = q.size();
        for(int j=0;j<node_count;j++){
            int parent = q.front();
            q.pop();
            
            q.push(parent - numbers[i]);
            q.push(parent + numbers[i]);
        }
    }
    while (!q.empty()) {
        if(q.front() == target) answer++;
        q.pop();
    }
}

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