[프로그래머스] BFS/DFS - 타겟 넘버

문제 설명

---

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 합니다.

내가 푼 답

---

function solution(numbers, target) {
    var answer = 0;

    dfs(0, 0); //dfs를 이용해서 풀어주자

    function dfs(sum, index) { //sum과 index값은 0이다.
        if (index === numbers.length) { 
		//index가 배열 number의 길이와 같아지면 모든 수를 사용한 것이므로 마감하고, 
            if (sum === target) {
			//sum과 target이 같은지 확인하고, 일치하면 answer에 1을 더해준다
                answer += 1;
            } 
            return;
        }
      // 재귀 호출인 현재 숫자를 더하고 빼며 밑의 트리로 넘어간다. 
        dfs(sum + numbers[index], index + 1);
        dfs(sum - numbers[index], index + 1);
    }
    return answer;
}

Code Flow

---

1) dfs(0, 0);은 깊이 우선 탐색(Depth-First Search, DFS)을 시작합니다.
dfs 함수를 최초로 호출하면서 초기 상태로서 현재 합 sum을 0으로, 현재 인덱스 index를 0으로 설정합니다.

2) function dfs(sum, index)는 주요 로직이 포함된 재귀 함수입니다.

• if (index === numbers.length)은 현재 인덱스 index가 배열 numbers의 길이와 같아지면, 모든 숫자를 사용한 것이므로 더 이상 숫자를 더하거나 빼는 작업을 진행하지 않고, 현재까지의 합 sum이 목표값 target과 일치하는지 확인합니다.
• if (sum === target)은 현재까지의 합 sum이 목표값 target과 일치하면, answer 변수를 1 증가시킵니다.
  return;은 함수를 종료하고 이전 호출로 돌아갑니다.

3) 재귀 호출부인 dfs(sum + numbers[index], index + 1);와
dfs(sum - numbers[index], index + 1);는 현재 숫자를 더하거나 빼며 다음 인덱스로 진행하는 작업입니다. 이렇게 재귀적으로 함수를 호출하면서 가능한 모든 조합을 검사합니다.

나는 잘 모르겠다. 자세히 해보자!

---

흑흑.. 어림도 없었다 ㅠㅠㅠ.. 하다 포기..