[JAVA] 프로그래머스 : 타겟 넘버

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

이 문제는 깊이 우선 탐색(DFS) 문제이다. 문제를 그려 보면 다음과 같다.
(물론 초반의 0은 문제에서 주어지지 않는다. 내가 이해하기 쉽도록 임의로 넣은 것이다.)

초반에는 +와 -를 어떻게 처리해 줄 것인지에 대한 시행착오를 많이 겪었다. -값을 붙여서 dfs의 index값으로 return해 주기도 하였는데, 아래 방법처럼 푸는 것이 가장 간단하고 직관적인 것 같다.

아예 index와 sum을 같이 매개변수로 넘겨 주고, 재귀함수를 통해서 풀면서 sum == target인 경우에만 정답 값을 1씩 증가시켜 주는 것이다.

여기서 중요한 점은, index가 배열의 끝 일 때에만 sum값과 target값을 비교해 주어야 하는 것이다. 그리고 target값으로 매개변수를 넘겨줄 때, 다음 요소를 더해주거나 빼 주어야 하니까 sum + numbers[index], sum - numbers[index]를 target값으로 넘겨 주면 된다. 이 때, dfs 함수를 각각 두 개를 호출하면 된다.

import java.util.*;

class Solution {
    private static boolean[] visited;
    private static int target;
    private static int answer = 0;
    private static int[] numbers;
    
    public int solution(int[] numbers, int target) {
        this.target = target;
        this.numbers = numbers;
        visited = new boolean[numbers.length];
        dfs(0,0);
        return answer;     
    }
    
    private void dfs(int index, int sum){
        if(index == numbers.length){
            if(sum == target){
                answer++;
            }
            return;
        }
        dfs(index + 1, sum + numbers[index]);
        dfs(index + 1, sum - numbers[index]);
    }

}