[프로그래머스 알고리즘] 타켓넘버 - 깊이탐색 DFS

프로그래머스 2단계 타겟넘버 문제

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

문제설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 

방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3

+1-1+1+1+1 = 3

+1+1-1+1+1 = 3

+1+1+1-1+1 = 3

+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 

return 하도록 solution 함수를 작성해주세요.

제한사항

주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

prices	target	return
[1, 1, 1, 1, 1]	3

자바코드

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

    public int DFS(int[] numbers, int target, int index, int num) {
        if(index == numbers.length) {
            return num == target ? 1 : 0;
        } else {
            return DFS(numbers, target, index + 1, num + numbers[index])
                    + DFS(numbers, target, index + 1, num - numbers[index]);
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[20];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = 1;
        }
        int target = 3;

        System.out.println(new Solution().solution(arr, target));
    }
}

문제설명

DFS 깊이탐색을 이용해서 문제를 풀어야 했다. DFS 문제는 Stack 또는 재귀를 통해 풀이가 가능하다. 나는 재귀를 이용해서 문제를 풀었다.

결국은 배열에 있는 요소가 하나의 노드라고 비유한다면, 배열의 인덱스는 깊이라고 비유할 수 있다. 결국은 각 깊이에 대해 모두 탐색하게 되고, 

모든 경우의 수를 모두 탐색하게 된다. 아래 이미지를 보면 이 문제를 DFS를 풀어야 하는 이유를 좀 더 잘 이해할 수 있을 것이다!

DFS에서는 점화식과 종료조건을 찾는 것이 가장 중요하다. 종료조건은 모든 깊이 즉, 배열에 모든 요소를 접근했을 때이다.

그리고 점화식은 해당 인덱스의 요소를 더할지, 혹은, 더하지 않을지의 모든 경우를 구하자! 이다.

 * 참고로 위의 트리는 https://yohasebe.com/rsyntaxtree/ 사이트에서 그렸다 (url 이동 가능)