[프로그래머스] 알고리즘 연습 문제 : 타겟 넘버 (자바/JAVA)

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

코딩테스트 연습 - 타겟 넘버 | 프로그래머스

class Solution {
    static int answer = 0;
    
    public int solution(int[] numbers, int target) {
       dfs(numbers, target, 0);
        return answer;
    }
 
    public static void dfs(int[] numbers, int target, int node) {
        if(node == numbers.length) {
            int sum = 0;
            for(int num : numbers) {
                sum += num;
            }
            if(sum == target) {
                answer++;
            }
        } else {
            numbers[node] *= 1;
            dfs(numbers, target, node+1);
 
            numbers[node] *= -1;
            dfs(numbers, target, node+1);
        }
    }
}

DFS, BFS에 대한 개념을 먼저 익히고 푸는게 좋은듯 싶다

(라고 상상함 하지만 어림도 없지ㅋㅋ 좀 더 익숙해지는 연습을 해야겠다...)

DFS, BFS를 한방에 이해하는 짤

DFS는 stack, 재귀함수로 구현할 수 있고,

BFS는 queue로 구현 가능하다

이제 저걸 코드로 풀어서 응용만 하면 되는데 쉽지 않았다 (뇌굳남, 뇌가 굳어버린 남자)

1) DFS를 활용해 해당 node의 숫자를 (+), (-)로 배열에 넣어준다. (Tree로 보면 한쪽엔 (+), 다른쪽엔 (-))

2) node가 해당 배열까지 탐색했다면, numbers 배열을 다 더한다.

3) target과 비교해서 일치하면 카운트 +1, 아니면 다시 탐색 후 반복