DFS(깊이우선탐색)

데이터의 구조는 선형구조, 비선형 구조로 이루어져 있는데 순차적으로 나열된 선형 구조에 비해 비선형 구조의 데이터는 탐색이 어렵다.

그때 사용하는 것이 DFS,BFS 탐색방법인데 우선은 DFS를 먼저 정리한다.

이 DFS방법은 두 가지의 방법이 있는데 첫 번째가 재귀이고, 두번째가 스택(반복문)을 이용하는 것이다.

DFS(Depth First Search)

 비선형 구조의 데이터에서 가장 깊은 노드까지 탐색하는 방법이다.

https://workat.tech/problem-solving/practice/dfs-of-acyclic-graph

- 탐색을 시작하는 노드를 스택에 넣고, 방문 처리를 한다.

- 방금 넣은 노드에 방문하지 않은 인접 노드가 있다면 인접노드로 이동하여 스택에 넣고 방문 처리를 한다.(반복)

- 만약 인접 노드가 없거나, 모든 노드를 방문했다면 스택에 쌓인 노드들을 pop한다.

- 이 방법을 반복하여 스택에 아무 것도 남아 있지 않을때까지 한다.

 

 

알고리즘 예시)  **재귀를 이용

let arr = [1, 3, 5, 6, 7, 10];
//여기 배열에서 숫자들을 빼서 다른 집합을 하나 만들때 다른 부분집합의 누적 값이 기존 베열에 남아있는 값들의 누적값과 같은지 확인
//만약 그런 값 경우가 있다면 "YES"를 return

//ex)
//arr=[1,3,5,7]  newArr=[6,10]

function solution(arr) {
  let answer = 'NO',
    flag = 0;
  let total = arr.reduce((a, b) => a + b, 0);
  let n = arr.length; //6

  function DFS(L, sum) {
    if (flag) return; //원하는 값이 있다면 더 이상 안 돌아도되므로 스탑
    if (L === n) {
      if (total - sum === sum) {
        answer = 'YES';
        flag = 1;
      }
    } else {
      DFS(L + 1, sum + arr[L]);
      DFS(L + 1, sum);
    }
  }

  DFS(0, 0);
  return answer;
}

let arr = [1, 3, 5, 6, 7, 10];
console.log(solution(arr));

javascript로 DFS 알고리즘을 공부하면서 확실히 어렵다고 많이 느끼고 있다.

지금 위에 코드도 stack 직접 그려가면서 이해했는데 익숙해지도록 꾸준히 반복해야겠다.

 

[코드 해석]

- 기존 arr의 배열을 다 더해서 total이라는 값에 넣어준다 (32)

- 하나씩 탐색해가며 sum에 다가 부분적인 값들을 더해 누적값을 넣어준다.

- total-sum = sum일 경우 "YES"를 리턴할 수 있도록 함

- 만약 이미 YES가 나왔다면 더 돌지 않도록 flag로 모두 return 해주기

 

 

참고블로그)

https://choonse.com/2022/02/16/945/

https://velog.io/@songyw0517/DFS%EB%9E%80-%EB%AC%B4%EC%97%87%EC%9D%B8%EA%B0%80