[javascript] 프로그래머스, 타겟넘버 (DFS)

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

1. 재귀로 dfs 함수를 구현

2. 트리를 상상해

3. 왼쪽 자식은, +를 계산해볼꺼구, 오른쪽 자식은 -를 계산해 볼꺼야
4. 계산해 보기위해서 재귀함수를 (플러스, 마이너스 각각..) 호출해서, 모든경우의 수를 확인하기!!

5. 종료조건은 배열을 다 돌았을 때? 트리 끝까지 들어갔을때~ (index가 배열의 길이인지 확인)

6. 그때 혹시 sum이 타겟과 같으면 답으로 카운팅~

 

function solution(numbers, target) {
    var 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;
}

 

 

어디서 퍼온 DFS와 BFS 의 비교 (언제 무엇으로 푸느냐?)

DFS
-> 검색 대상 그래프가 큰 경우 (정점과 간선의 개수가 많음)
-> 경로의 특징을 저장해둬야 하는 문제
ex) 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는 데 경로에 같은 숫자가 있으면 안된다는 문제
(BFS는 경로의 특징을 가지지 못함)

BFS
-> 미로찾기 등 최단거리를 구해야 할 경우 (DFS는 처음으로 발견되는 해답이 최단거리 라는 것이 보장이 안된다.
반면 BFS는 현재 노드에서 가까운 곳부터 찾기 때문에 경로 탐색 시 첫번째로 찾아지는 해답이 곧 최단거리이다.)

DFS BFS 둘 다 적합한 경우
-> 단순히 모든 정점을 방문하는 것이 중요한 문제인 경우 어떤 것을 택해도 된다.

 

그림을 잘 그려놓은 블로그가 있었는데.. 흠..

 

트리에 숫자를 써놓으셨는데 플로우 이해에 도움이 된다.
사진이 나오셔서 부담스럽네;

프로그래머스 Level 2 - 타겟 넘버 (JavaScript)

이것도 비슷 !

[프로그래머스] 타겟 넘버 (javascript)