[Programmers/JAVA] 타겟 넘버

내 코드

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        
        answer=dfs(numbers, target, 0, 0);
        
        return answer;
    }
    
    //깊이 우선 탐색(dfs) 방식 메소드. 계속해서 아래로 내려감!
    public static int dfs(int[] numbers, int target, int line, int sum) {
        if(line== numbers.length) {
            if(sum==target) {
                return 1;
            }
            return 0;
        }

        return dfs(numbers, target, line+1, sum+numbers[line])+
                dfs(numbers, target, line+1, sum-numbers[line]);
    }
}

 

느낀점

내가 DFS/BFS 를 처음 접해봐서 쉽진 않았다. 개념까지 익히고 문제를 풀어야하는건 항상 어렵다. 하지만 그만큼 남는게 많아서 풀고나면 뿌듯하기도하다.

이 문제는 주어진 numbers 배열의 항목들을 차례차례 더해주거나 빼면서 그 값이 target과 동일한가 확인하는 문제였다. 너비 우선 탐색(BFS)은 가까운 노드를 우선적으로 탐색하고 깊이 우선 탐색(DFS)은 깊은 부분을 우선적으로 탐색한다. 한 줄씩 계산을 하고 다음으로 넘어가야하는 이 문제는 깊이 우선 탐색이 알맞을 것 같아 DFS로 해야겠다고까지는 생각했다. 근데 그 다음... 그래서 어떻게 계산 할건데..!? 다른 사람의 풀이를 참고하는게 제일 나은 방법일 것 같아 참고했다. dfs메소드에 한번 들어가면 line(index? 라고 해야하나)이 numbers의 length와 같아 질때까지 재귀함수로 계속 반복된다. numbers의 length와 line이 같아지면 sum이 (재귀함수를 반복하면서, line이 length와 같아질때까지, 계속해서 +와 -를 반복하며 계산됨) target과 같은지 확인하고 target과 같다면 answer에 1씩 더해진다.

방법을 이해하면 쉬워보인다. 재귀함수를 사용하는 방법을 잘 못익혔었는데 이런 식으로 사용하면 된다는 것을 배웠다. 여러모로 남는게 많은 고마운 문제였다.