*[JS] 깊이/너비 우선 탐색(DFS/BFS) > 타겟 넘버
function solution(numbers, target) {
let answer = 0;
const length = numbers.length;
function dfs(count, sum, flag) {
if (count === length) {
if (target === sum) {
answer++;
}
return;
}
dfs(count + 1, sum + numbers[count]);
dfs(count + 1, sum - numbers[count]);
}
dfs(0, 0);
return answer;
}이번 문제는 도저히 감이 안 잡혀서 다른 분의 코드를 참고했다.
DFS, BFS는 들어는 봤지만 어떤 식으로 코드를 구현하는지 몰랐고, 그래서 코드푸는 힌트를 보아도 구현조차 할 수가 없었다..ㅠ 재귀도 잘 안 써서 더 막막했던...
[프로그래머스] 타겟 넘버 (javascript)
문제
jjnooys.medium.com
이 분의 코드와 풀이법을 참고했다!
numbers가 [1,1,1,1,1]이고 target이 3일 때 숫자의 순서는 그대로 두고 플러스인지 마이너스인지만 변경해서 배열의 합이 target이 되게 해야 한다.
그렇다면 경우의 수는 2^5가 될 것이고 이 모든 경우의 수를 실행하면서 target이 될 때만 카운트를 올려 그 값을 리턴해야 한다.
//length = 5, target = 3
function dfs(count, sum, flag) {
if (count === length) {
if (target === sum) {
answer++;
}
return;
}
dfs(count + 1, sum + numbers[count]);
dfs(count + 1, sum - numbers[count]);
}dfs함수는 count (배열의 인덱스로 사용됨), sum(요소의 합), flag(플러스/마이너스 표시:흐름을 위해 임의로 표시함)를 매개변수로 받는다.
만약 count가 length와 같아졌다면 배열의 모든 값을 순회했다는 뜻으로 이 경우에만 그 합이 target과 일치하는지를 확인한다.
조건 탐색이 끝이 났다면 재귀함수를 실행하게 되는데 count는 1씩 올리고 sum에는 각 요소의 값을 더하거나 빼주는 식으로 순회를 한다.
가장 처음 dfs(0,0)을 넣어 함수를 실행해준다.
count가 0, length는 5이기 때문에 조건을 타지 않고 바로 dfs(count+1, sum + numbers[count])를 실행한다.
즉 dfs(0+1, 0 + 1(=numbers[0]))가 되어 dfs(1,1)가 된다.
count가 1일 때도 length와 다르게 되어 다시 dfs함수를 실행한다
dfs(2,2), dfs(3,3), dfs(4,4)까지는 count==length가 false이기 때문에 계속 플러스 재귀를 호출한다. (=>배열의 모든 값이 사용되지 않음!)
dfs(5,5)일 때는 count==length가 true가 되어 안의 target===sum을 체크하게 되지만 target은 3이고 sum은 5이기 때문에 answer가 더해지지 않고 바로 리턴이 된다.
dfs(5,5) 이 경우는 +1 +1 +1 +1 +1를 뜻한다.
리턴이 되면 dfs(count+1, sum - numbers[count])인 마이너스 재귀를 타게 되는데 이때 리턴을 했기 때문에 count는 4가 되어 dfs(4+1, 4-1)로 dfs(5, 3)이 호출된다.
count와 length가 동일하고, target과 sum도 동일해져서 answer가 플러스된다.
이 경우는 +1 +1 +1 +1 -1 를 뜻한다.
리턴이 되면 count는 3이 되어 dfs(4, 2)를 호출한다.
이 때는 count와 length가 다르기 때문에 플러스 재귀를 호출해 dfs(5,3)이 된다.
이 경우는 +1 +1 +1 -1 +1 을 뜻한다.
이런 식으로 깊이탐색은 요소 1에 대해 플러스에 대해 모든 값을 확인하고, 그 값이 조건을 만족하지 않으면 마이너스를 탐색하는 식으로 진행이 된다.
+ + + + +
+ + + + -
+ + + - +
+ + + - - ... 이런식으로 계속 반복해
- - - - - 가 될 때까지 노드를 순회해 타겟이 되는 경우의 수를 찾는다.
