[프로그래머스] 깊이/너비 우선 탐색(DFS/BFS). 타겟 넘버

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 이하인 자연수입니다.

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

입출력 예 설명

입출력 예 #1
문제 예시와 같습니다.

입출력 예 #2
+4+1-2+1 = 4
+4-1+2-1 = 4
총 2가지 방법이 있으므로, 2를 return 합니다.

DFS 문제입니다. DFS 문제는 쉽지 않다고 생각하는데요. 적응이 되도록 반복해서 풀어야겠습니다.

 

문제 풀이는 재귀를 사용했습니다. dfs 메서드 안에서 depth를 양수로 한번, 음수로 한번 재귀하여 모든 경우의 수를 반복합니다. 모든 경우의 수를 보고 target과 같은 배열의 합이 나온다면 answer를 1 증가시키도록 합니다.

 

코드는 간단하나 생각하는게 쉽지 않습니다. DFS 문제가 모두 그런거 같네요. 아래는 소스코드 입니다.

 

public class TargetNumber {
    private int answer = 0;

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

    private void dfs(int[] numbers, int depth, int target) {
        if (depth == numbers.length) {
            int sum = 0;

            for (int number : numbers) {
                sum += number;
            }

            if (sum == target) {
                answer++;
            }
            return;
        }

        dfs(numbers, depth + 1, target);
        numbers[depth] = numbers[depth] * -1;
        dfs(numbers, depth + 1, target);
    }
}