[Lv2] 타겟넘버

프로그래머스

• https://programmers.co.kr/learn/courses/30/lessons/43165

이 문제는 DFS 알고리즘을 사용해 풀 수 있는데, DFS에서 재귀함수를 작성하는 것에 익숙하지 않아 다른 분의 풀이 프로그래머스 타겟 넘버를 보고 이해했다.

문제이해

n개의 요소를 갖는 numbers의 요소를 더하거나 빼서 target을 만들 수 있는 경우의 수를 리턴해야한다. 각 요소는 + 또는 -를 할 수 있으므로 총 2^n가지 경우의 수를 만들 수 있다.

DFS

여기서 사용할 수 있는 방식은 재귀함수를 사용한 DFS(깊이우선탐색) 알고리즘이다.

하나의 노드를 끝까지 탐색한 후, 더이상 자식노드가 없을때 인접한 상위노드의 형제노드를 방문한다. 형제 노드에서도 자식노드를 탐색하고, 더 이상 자식노드가 없을때, 인접한 상위노드의 형제노드를 방문한다.

풀이

function solution(numbers, target) {
  let answer = 0;
  dfs(0,0);
  
  function dfs(index, sum) {
    if(index === numbers.length) {
      if(sum === target) {
        answer++
      }
      return;
    }
    dfs(index+1, sum+numbers[index]);
    dfs(index+1, sum-numbers[index]);
  }
  return answer;
}

예시

다음은 solution([1,1,1,1,1],3)을 실행한 예시이다.

🔍 마지막 자식노드까지 확인하기

dfs 함수가 호출됨에 따라 콜스택을 확인해보면, 생성한 dfs 함수가 차례로 쌓이고, 마지막 index=5, sum=5인 경우에 조건(index===numbers.length)에 해당되어 answer++가 되고, 함수가 리턴되고, 콜스택에서 pop된다.

🔍 상위 형제노드의 마지막 자식노드까지 확인하기

dfs(5,5)가 리턴된 후에 콜스택에 쌓여있던 가장 마지막 함수인 dfs(4,4)에 대해 dfs(4+1, 4-1)이 실행된다. dfs(5,3)은 조건문을 모두 만족하므로 answer++되고 리턴된다.

👉 여기서 dfs(4,4)는 dfs(5,5)의 상위의 형제노드에 해당한다.

🔍 모든 노드의 모든 자식노드까지 확인하기

각 노드의 마지막 +, 마지막 -까지 모두 확인했다면 answer를 리턴한다.