[JavaScript] 자바스크립트 DFS 문제풀이 예시

DFS(깊이 우선 탐색)는 재귀를 이용한 방식이며, 우선 한 노드의 끝까지 탐색해야 한다면 이용합니다.

• 주어진 숫자들을 모두 이용하여 어떤 값을 만들어내야 하는 문제
• 값들이 주어지고, 어떤 특정한 결과를 얻기 위해 얼마나 많은 방법이 있는지 도출해야 하는 문제
• 미로 찾기 문제

이런 문제들은 트리의 마지막 레벨까지, 그리고 가끔은 모든 구성요소를 탐색해서 그 결과들끼리 비교를 하거나 하기 때문에 DFS를 많이 이용합니다.

 

 

문제 출처 : 프로그래머스 Lv.2 '타겟 넘버'

 

function solution(numbers, target) {
    let count = 0;
    
    const dfs = (lv, val) => {
        if (lv === numbers.length) {
            if (val === target) {
                count++;
            }
        } else {
            dfs(lv + 1, val + numbers[lv]);
            dfs(lv + 1, val - numbers[lv]);
        }
    }
    
    dfs(0, 0);
    
    return count;
}

 

함수 안에 함수를 넣을 수 있다는 사실...

 

 

Solved-Algorithm/JavaScript/프로그래머스/2/43165. 타겟 넘버 at 2b2684ecdb0ad8fced9a05e302d17434095d37b8 · ParkBib