bfs dfs 프로그래머스 타겟 넘버 문제

js

 

numbers = [n,n,n,n,n];

target = n;

ex) func([1,1,1,1,1],3);

 

function bfs(numbers, target) {

let answer = 0;

getAnswer(0, 0);

function getAnswer(x, value) {

if (x < numbers.length) {

getAnswer(x + 1, value + numbers[x]);

getAnswer(x + 1, value - numbers[x]);

} else {

if (value === target) {

answer++;

}

}

}

return answer;

}

 

function bfs(numbers, target) {

let answer = 0;

let tmp = numbers.shift();

let q = [-tmp, +tmp];

numbers.map((v, i) => {

console.log('v: ' + v + ' i ' + i);

let q_tmp = [];

while (q.length > 0) {

console.log('q : ' + q);

let element = q.shift();

if (i == numbers.length - 1) {

if (element - v == target || element + v == target) {

console.log('element : ' + element + ' / v : ' + v);

answer++;

console.log('answer : ' + answer);

continue;

}

}

// console.log('이전 : ' + q_tmp);

q_tmp.push(element - v);

q_tmp.push(element + v);

console.log('이후 : ' + q_tmp);

}

q = q_tmp;

});

 

return answer;

}