[DFS/BFS] 타켓 넘버 - JAVA

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

프로그래머스

---

이제 DFS/BFS 문제 보면 아 이거 DFS다 이정도 감은 온다

근데 어떻게 쓰지...?에서 항상 고장남🤓

 

그래도 막 어렵진 않았고 다른 풀이 살짝 참고해서 풀었다..^^

 

dfs는 주로 재귀함수로 구현되기 때문에 탈출 조건이 필요하다

그래서 depth 라는 변수를 이용해서 numbers의 마지막 노드일 경우 지금까지 더한 값인 sum과 target을 비교하여 같으면 answer를 1씩 더해주도록 하였다

 

그리고 마지막 노드가 아니라면 다음 노드를 탐색해야 하기 때문에 재귀호출을 하는데, 여기서 현재 값의 부호가 +인지 -인지에 따라 달라지기 때문에 2가지를 모두 호출한다

 

이게 끝임...ㅎㅎ

아무래도 레벨 2라 그런지 엄청 어렵진 않은듯!

근데 왜 혼자 못푸냐고 엉엉😭

 

 

 

자바 코드)

public class Solution {
    static int answer = 0;
    
    public int solution(int[] numbers, int target) {
        dfs(numbers, target, 0, 0);
        return answer;
    }
    public static void dfs(int[] numbers, int target, int depth, int sum) {
        if(numbers.length == depth) { //마지막 노드 탐색
            if(sum==target) {
                answer++;
            }
        } else {
            dfs(numbers, target, depth+1, sum+numbers[depth]);
            dfs(numbers, target, depth+1, sum-numbers[depth]);
        }
    }
}