[프로그래머스 | Java Lv.2] [복습] 타겟 넘버(dfs/bfs)

문제

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

프로그래머스

---

package week6.baek.dfsbfs;

public class TargetNumber {
    static int count = 0;
    public static int solution(int[] numbers, int target) {
        dfs(numbers,target, numbers[0], 1);
        dfs(numbers, target, -numbers[0], 1);

        return count;
    }

    public static void dfs(int[] numbers, int target, int result, int depth){
        if(depth == numbers.length - 1){
            if (result + numbers[depth] == target || result - numbers[depth] == target) {
                count++;
                return;
            }
        }

        else {
            dfs(numbers, target, result - numbers[depth], depth + 1);
            dfs(numbers, target, result + numbers[depth], depth + 1);
        }
    }

    public static void main(String[] args) {
        int[] numbers = {1,1,1,1,1};
        System.out.println(solution(numbers, 3));
    }
}

 

이렇게 처음엔 했었는데 생각해보니 result=0, depth=0일 때로 시작하는게 더 깔끔하겠다

 

최종 코드

package week6.baek.dfsbfs;

public class TargetNumber {
    static int count = 0;
    public static int solution(int[] numbers, int target) {
        dfs(numbers,target, 0,0);

        return count;
    }

    public static void dfs(int[] numbers, int target, int result, int depth){
        if(depth == numbers.length - 1){
            if (result + numbers[depth] == target || result - numbers[depth] == target) {
                count++;
                return;
            }
        }

        else {
            dfs(numbers, target, result - numbers[depth], depth + 1);
            dfs(numbers, target, result + numbers[depth], depth + 1);
        }
    }

    public static void main(String[] args) {
        int[] numbers = {1,1,1,1,1};
        System.out.println(solution(numbers, 3));
    }
}