[JAVA] 프로그래머스 : 타켓 넘버 (코딩테스트 고득점 kit > 깊이/너비 우선 탐색(DFS/BFS))

https://programmers.co.kr/learn/courses/30/lessons/43165?language=java

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

 

해결 방안

1. number 배열의 숫자를 계속 빼거나 더하는 두 가지 경우로 나눠져서 DFS를 이용하여 풀었음

2. DFS index가 numbers.length 까지 오게 되면 numbers에 쌓인 값들을 다 더해 sum을 구하고 그 sum이 target과 같으면 answer를 ++ 해줌

 

코드

// 타겟 넘버
class Solution {
    public static int answer = 0;
    
    public static void dfs(int[] numbers, int target, int index){
        if(index == numbers.length){
            int sum = 0;
            
            for(int i=0; i<numbers.length; i++){
                sum += numbers[i];
            }
            if(sum == target)
                answer++;
        }
        // 더하거나 빼거나 두 경우
        else{
            numbers[index] *= 1;
            dfs(numbers, target, index+1);
            
            numbers[index] *= -1;
            dfs(numbers, target, index+1);
        }
    }
    
    public int solution(int[] numbers, int target) {
        
        dfs(numbers, target, 0);
        
        return answer;
    }
}