타겟 넘버 - DFS/BFS [프로그래머스 고득점 Kit]

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

프로그래머스

 

DFS, BFS란 ?

DFS(Depth-First Search)와 BFS(Breadth-First Search)는 그래프 탐색 알고리즘 중 가장 기본적인 두 가지 방법이다.

이 둘은 각각 다른 방식으로 그래프를 탐색합니다.

DFS (깊이 우선 탐색)

DFS는 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 특정 노드에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색한다. 이러한 방식으로 깊이를 우선하여 탐색하기 때문에 스택(Stack) 자료구조를 사용한다. 재귀(Recursion)를 이용하여 구현할 수도 있다.

BFS (너비 우선 탐색)

BFS는 그래프의 가까운 부분을 우선적으로 탐색하는 알고리즘이다. 특정 노드에서 시작하여 해당 노드와 인접한 모든 노드를 우선 탐색한다. 이후에는 해당 인접 노드들부터 다시 너비 우선 탐색을 진행한다. 이러한 방식으로 너비를 우선하여 탐색하기 때문에 큐(Queue) 자료구조를 사용한다.

차이점

1. 탐색 방식: DFS는 깊이를 우선하여 탐색하고, BFS는 너비를 우선하여 탐색한다.
2. 자료구조: DFS는 스택(Stack) 또는 재귀(Recursion)를 통해 구현되며, BFS는 큐(Queue)를 사용한다.
3. 탐색 시간: DFS는 깊이를 탐색하기 때문에 깊은 부분을 우선 탐색하므로 목표 노드가 깊은 부분에 있는 경우 효율적이다. 반면 BFS는 가까운 부분을 먼저 탐색하기 때문에 목표 노드가 깊은 부분에 있을 때까지 모든 노드를 탐색해야 할 수 있으나, 목표 노드가 깊지 않은 경우 효율적이다.

DFS와 BFS는 각각의 장단점이 있으며, 문제의 특성에 따라 적합한 알고리즘을 선택하여 사용해야 한다.

 

이 문제 풀이는 DFS를 활용한다.

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;
}