[lv.2] 타겟 넘버

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

• 문제
  

• 풀이
  어...사실 풀이랄 것도 없다.
  다음으로 넘어가는 선택지가 +인지 -인지, 결국 2가지이기에 DFS나 BFS로 두 가지 경우를 모두 넣어주면 된다.
  성능으론 DFS가 압도적이다. (왜그런지는 모르겠다.)

• 코드 (BFS)

import java.util.*;

class Solution {
    public int solution(int[] num, int target) {
        int answer = 0;
        answer = bfs(num, target);
        return answer;
    }
    public int bfs(int[] num, int target){
        int cnt = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{num[0], 0});
        queue.add(new int[]{-1*num[0], 0});
        while(!queue.isEmpty()){
            int[] now = queue.poll();
            if(now[1]==num.length-1){
                if(now[0]==target) cnt++;
                continue;
            }
            queue.add(new int[]{now[0]+num[now[1]+1], now[1]+1});
            queue.add(new int[]{now[0]-num[now[1]+1], now[1]+1});
        }
        return cnt;
    }
}

• 코드 (DFS)

import java.util.*;

class Solution {
    static int cnt = 0;
    public int solution(int[] num, int target) {
        int answer = 0;
        dfs(num, target, num[0], 0);
        dfs(num, target, -1*num[0], 0);
        answer = cnt;
        return answer;
    }
    public void dfs(int[] num, int target, int now, int depth){
        if(depth==num.length-1){
            if(now==target) cnt++;
            return;
        }
        else{
            dfs(num, target, now+num[depth+1], depth+1);
            dfs(num, target, now-num[depth+1], depth+1);
        }
    }
}

• DFS vs BFS