[Javascript] DFS 부분집합 만들기

부분 집합

수학 싫어하면 패스 😅
중고등학교 수학시간에 1,2,3을 가지고 부분집합을 만들려면 포함/미포함 2가지 경우를 3번 곱해서 (곱의법칙) 2x2x2 = 8가지의 경우의 수가 나온다고 배웠습니다. 이는 두가지 경우의 수를 3번 시행하는거라 뎁스4의 이진 트리와 같습니다.

모르겠고 그냥 구현하고 싶다면

수학적인 내용 모르겠고 그냥 구현만 하려면 아래 코드를 보시면 됩니다.
지금 내 수준으로 간단하게 DFS를 이야기해보면 DFS 함수 내에는 2가지 로직부분이 존재합니다.

1. if문을 통해 예외처리를 하거나 마지막 처리를 해주고 (basecase)
2. 탐색을 하는 부분 (순서가 중요함)

그래서 부분집합 탐색에서 어쩃든 포함/미포함, 1/0으로 트리가 나누어 질수 있다는 걸 깨닫고, 1로 탐색하는 방향, 0으로 탐색하는 방향 2갈래를 만들어 로직을 처리하면 된다는 걸 깨달으면 문제 해결이 가능합니다.
이렇게 해결 과정을 알기 까지가 어렵지, 탐색 로직만 이해되면 베이스케이스 부분에서 로직 처리하는 건 간단한 구현이라 크게 어렵지 않습니다. 아직 DFS 문제라고 보기엔 너무 기본 예제만 해보는 중이지만 6개월전 처음 그래프 탐색을 배워봤을 때보단 훨씬 났네요.

내 풀이

  function solution(n) {
    const answer = [];
    const ch = Array.from({ length: n + 1 }, () => 0);

    function DFS(v) {
      if (v === n + 1) {
        let tmp = '';
        ch.forEach((x, i) => {
          if (x === 1) {
            tmp += i + ' ';
          }
        });

        answer.push(tmp.trim());
        return;
      }
      ch[v] = 1;
      DFS(v + 1);
      ch[v] = 0;
      DFS(v + 1);
    }

    DFS(1);

    return answer;
  }

  console.log(solution(3));

else 문 없이 if문에서 return 해줘야 더 깔끔하지만, 자꾸 return 문 적는걸 까먹다 보니 그냥 else로 묶는게 나은가 생각중입니다. 그래도 else문 지우는게 깔끔합니다.
부분집합 구하기는 이전에 순열 조합 구하기에서도 너무 구현하고 싶었지만 머리가 아파서 못구했었습니다. 단순히 머리가 안좋다고 생각했지만… 재귀기본부터 차근차근 공부하고 코드도 보고 하니 완벽하게 알진 못해도 구현이 가능한 수준이 되었습니다.

코드 설명

1) DFS 함수 안에 else 문이 탐색 로직입니다. ch 라는 체크 배열을 만들고, (0000) 해당 배열의 v인덱스의 값을 1일때 DFS 돌리고, 0일 때 돌리는 식으로 0과 1 모두 재귀 돌도록 해줍니다.
1-1) 체크 배열을 만드는 방법은 위와 같이 Array.from({ length: n + 1}, () ⇒ 0) 처럼 해주면 n + 1 길이의 0으로 채워진 배열이 만들어집니다.
2) if 문 안은 마지막 부분에서 정답을 만들어주는 부분입니다.
2-1) 체크배열을 순회하면서 1로 체크 된 애들만 담아서 answer 배열에 담아줍니다.
3) 한바퀴 돌고 나면 부분집합으로 모든 경우의 수가 체킹됩니다.