[알고리즘] DFS/BFS 알기

<< DFS, BFS 는 기업 코테에서 무조건 나오는 문제인거 같다.. 그래서 많이 풀어봐야겠다 느껴서 작성해보려한다. >>

🚀 DFS, BFS 는 무슨 차이이며 언제 사용할까??

DFS 는 앞 글자 'D' 를 보면 알 수 있듯이 Depth 즉, 깊이 우선 탐색이다. 그래프에서 깊이를 나타낸다면 루트 노드에서 리프 노드까지 가야된다. 따라서 모든 경로를 탐색해야할 때 유용하다고 볼 수 있다.

반면 BFS 는 Breadth 로, 너비 우선 탐색이다. BFS 는 DFS 와는 다르게 최단 거리, 최소 횟수를 구해야할 때 유용하다고 할 수 있다.

🚀 DFS, BFS 는 어떤식으로 풀이할 수 있을까??

DFS 는 모든 경로를 계산해야되기 때문에 재귀나 스택으로 구현을 해야하며 BFS 는 큐를 이용해 구현할 수 있다.
그럼 프로그래머스 코테 문제를 통해 익숙해져보자..!

🚀🚀 DFS/BFS 문제

링크텍스트

위 문제를 DFS/BFS 두 가지 방법 모두 이용해 풀어보겠다.

🚀 DFS 방법

function solution (numbers, target) {
    let count = 0;
    function dfs ( index, sum ) {
        if (index === numbers.length) {
            if (sum === target){
                count ++
            }
            return;
        }
    dfs (index +1, sum+numbers[index])    
    dfs (index +1, sum-numbers[index])        
    }
    dfs(0,0)
    return count
}

dfs 를 그래프로 나타내면 위와 같다. (0,0) 부터 시작해서 +1, -1 를 추가하며 5번째까지 재귀를 돌고 target 값과 같으면 count++ 를 해주었다.

🚀 BFS 방법

function solution(numbers, target) {
  let queue = [[0, 0]]; 
  let count = 0;
  while (queue.length > 0) {
    let [sum, index] = queue.shift(); 
    if (index === numbers.length) {
      if (sum === target) count++;
    } else {
      queue.push([sum + numbers[index], index + 1]); 
      queue.push([sum - numbers[index], index + 1]);
    }
  }
  return count;
}
}

BFS 를 사용하는 이유는 DFS 의 위험성 때문이기도 한데, DFS 는 결국 재귀 호출을 하기 때문에 조건의 수가 높다면 스택 오버플로우가 발생할 수도 있기 때문에 조건에 따라 잘 쓰는게 중요한거 같다..! (하지만 결국 둘다 시간복잡도는 동일해서.. 더 좋은 Map 을 이용해서 풀이를 하기도 한다..)

이 문제 말고 더 풀어보고 올려보도록 하겠다!