DFS

스택과 재귀

• 깊게 탐색 하는 것이다.
• 계속 내려가다 더 이상 갈 수 없게되면 다시 가장 가까운 갈림길로 돌아온다
• 사용하는 경우 : 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.
• BFS보다 간단하다.
• BFS에 비해서 느리다
  
  
  
  
  
  

BFS

큐를 사용

• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어진 정점을 나중에 방문하는 순회방법이다.
• 넓게 탐색
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택(모든 노드 아닌)
  
  
  
  
  
  

DFS VS BFS

• DFS 는 스택(혹은 재귀) , BFS 는 큐를 사용한다.
• BFS는 재귀적으로 동작하지 않는다.

  최단 거리 문제를 푼다면 BFS를 사용합니다.
  이동할 때마다 가중치가 붙어서 이동한다거나 이동 과정에서 여러 제약이 있을 경우 DFS로 구현하는 것이 좋습니다.

Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

구현

다음과 같은 로직을 생각하고 구현하였다.

• add - div 함수를 나누어 구현

function solution(numbers, target) {
  let answer = 0;
  let count = 0;
  function add(number, count) {
    if (numbers.length - 1 === number) {
      if (count === target) {
        answer++;
      }
      return;
    }
    add(number + 1, count + numbers[number + 1]);

    div(number + 1, count - numbers[number + 1]);
  }
  function div(number, count) {
    if (numbers.length - 1 === number) {
      if (count === target) {
        answer++;
      }
      return;
    }
    add(number + 1, count + numbers[number + 1]);

    div(number + 1, count - numbers[number + 1]);
  }
  add(0, count + numbers[0]);

  div(0, count - numbers[0]);
  return answer;
}
solution([1, 1, 1, 1, 1], 3);

• 한개의 함수로 구현
  사실 두개의 함수로 구현하는 경우 각 함수에서 더하기 빼기 작업을 해야함.
  다음은 더하기 빼기 작업을 한 후 인자로 보내는 방식( 하나의 함수로 구현 )

function func(number, count) {
    if (numbers.length - 1 === number) {
      if (count === target) {
        answer++;
      }
      return;
    }
    func(number + 1, count + numbers[number + 1]);
    func(number + 1, count - numbers[number + 1]);
  }
  func(0, +numbers[0]);
  func(0, -numbers[0]);

Reference

• https://covenant.tistory.com/132
• https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html