프로그래머스 - 타겟 넘버

정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조인 그래프를 탐색하는 방법에는 DFS와 BFS가 있다.

DFS(Depth First Search) : 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하기 탐색하는 방식
모든 노드를 방문하고자 할 때 사용
비교적 간단하지만 느리다
스택 또는 재귀함수로 구현

BFS(Breadth First Search) : 시작 정점을 기준으로 인접한 노드들을 먼저 탐색하는 방식
주로 최단경로를 탐색하고자 할 때 사용
큐로 구현

이 문제에서는 모든 경우를 탐색해야 하기 때문에 DFS를 사용한다.

---

1. 재귀함수 풀이

public class Test_32_TargetNumber {
    public int solution(int[] numbers, int target) {
        return dfs(numbers, target, 0, 0);
    }

    private int dfs(int[] numbers, int target, int index, int sum) {
        if (index == numbers.length) {
            if (sum == target) {
                return 1;
            } else {
                return 0;
            }
        }
        
        int count = 0;
        count += dfs(numbers, target, index + 1, sum + numbers[index]);
        count += dfs(numbers, target, index + 1, sum - numbers[index]);
        
        return count;
    }
}

2. Stack 풀이

public class Test_32_TargetNumber {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[] {0, 0});

        while (!stack.isEmpty()) {
            int[] current = stack.pop();
            int index = current[0];
            int sum = current[1];

            if (index == numbers.length) {
                if (sum == target) {
                    answer++;
                }
            } else {
                stack.push(new int[] {index + 1, sum + numbers[index]});
                stack.push(new int[] {index + 1, sum - numbers[index]});
            }
        }

        return answer;
    }
}