[JavaScript] DFS 상태 트리

https://doringri.tistory.com/92

[Python] DFS(깊이우선탐색) 알고리즘

위는 파이썬 코드 버전.

 

const n = 3;
const ch = Array(n).fill(0);

function DFS(v) {
  if (v === n) { // n까지 갔을때 종료
    const subset = [];
    
    for (let i = 0; i < n; i++) { // 0에서 n까지
      if (ch[i] === 1) subset.push(i + 1);
    }
    
    console.log(subset);
    return;
  }

  ch[v] = 1; // 포함
  DFS(v + 1);

  ch[v] = 0; // 미포함
  DFS(v + 1);
}

DFS(0);

 

 

---

부분집합을 구하는 경우는 생각보다 많은 것 같다...

BFS랑 같이 암기해두자.