DFS (Depth-First Search)

: 루트 노드 (혹은 임의의 노드)에서 시작해 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색

• 미로를 탐색할 때 한 방향으로 갈 수 있는 곳까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와 다른 방향으로 다시 탐색을 진행하는 방법과 유사
• "넓게 탐색하기 전에 깊게 탐색"
• 모든 노드를 방문하고자 할 때 이 방식 사용

DFS 특징

• 자기 자신을 호출하는 순환 알고리즘의 형태
• 전위 순회 ( pre-order traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류
• 무한 루프 발생 방지를 위해 노드의 방문 여부를 반드시 검사

DFS 과정

재귀호출

⊙ v: 현재 방문중인 노드, u: 아직 방문하지 않은 노드
① 그래프의 시작 노드 v에서 출발해 방문 여부를 표시한다.
② v에 인접한 노드들 중에서 아직 방문하지 않은 노드 u를 선택한다.
③ 만약 인접한 노드가 없거나 이미 방문한 노드들만 존재한다면 탐색을 종료한다.
④ 탐색을 종료했을 때 방문하지 않은 노드 u가 있다면 u를 시작노드로 해 깊이 우선 탐색을 다시 시작한다.
⑤ 이 탐색이 끝나면 다시 v에 인접한 노드들 중에서 아직 방문안된 노드를 찾는다.
⑥ 없을 경우 종료하고, 있다면 다시 그 노드를 시작노드로 하여 깊이 우선 탐색을 시작한다.

stack 사용

① 탐색 시작 노드를 stack에 삽입하고, 방문처리
② stack의 top노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 stack에 넣고 방문처리
③ 방문하지 않은 노드가 없으면 stack pop
④ ③번 과정 수행할 수 없을 때까지 반복

DFS를 활용한 알고리즘 문제 풀이

타겟 넘버

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

solution code

function solution(numbers, target) {
  let answer = 0;
  const num = numbers.length;

  const dfs = (cnt, sum) => {
    if (cnt === num) {
      if (target === sum) answer++;
      return;
    }
    dfs(cnt + 1, sum + numbers[cnt]);
    dfs(cnt + 1, sum - numbers[cnt]);
  };

  dfs(0, 0);

  return answer;
}

(생략된 과정 있을 유..)