프로그래머스-타겟 넘버

DFS/BFS 등 탐색문제가 헷갈려 해당 문제를 통해 정리해두려 한다.

숫자 배열과 타겟 넘버를 input받으면 배열 내 숫자를 적절히 더하거나 빼서 타겟 넘버와 같아지는 경우의 수를 구하는 문제이다.

{1, 1, 1, 1, 1} 와 3이 입력되었을 때 아래와 같이 경우의수를 계산하여 5가 return되면 문제를 올바르게 해결한 것이다.

-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

배열 내 모든 숫자들의 부호를 결정해주어 모든 경우의 수를 탐색하려면 DFS 또는 BFS 알고리즘을 이용해야한다.

node는 depth를 의미하는 변수로 지정했다.

node(depth)가 9가 되어 최하위 child까지 도달했다면 이제 배열의 합을 구하고 이를 타겟 넘버와 비교하면 된다.

Kideveloper