부분집합 구하기(DFS)

 

 

문제

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램 을 작성하시오.

 

🍔입력설명

첫 번째 줄에 자연수 N(1<=N<=10)이 주어진다.

 

🍔출력설명

첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다.

단 공집합(∮)은 출력하지 않는다. (공집합은 아무런 원소를 가지지 않는 집합이다)

 

🍔입력예제 1

3

 

🍔출력예제 1

1 2 3

1 2

1 3

1

2 3

2

3

풀이

1. 정답을 반환하기 위한 answer 배열변수를 생성한다.

2. 부분집합이 있는지 확인하기위한 check 배열변수를 생성한다.

  - DFS 함수를 쓸 때 인자값이 1부터 들어가기 때문에,

    check 배열변수를 solution함수에 들어간 인자보다 1 더 큰 길이로 만든다.

3. solution함수에서 DFS(1) 함수를 호출한다.

4. DFS 재귀함수에서 만약에 DFS인자 값이 solution인자값+1이면 answer 배열에 반복문을 돌려 해당하는 값을 넣는다.

5. 4번의 조건이 아니라면 아래와 같이 한다.

check[level] = 1 // 부분집합 level(1~n) 이 있다는 뜻
DFS(level + 1)
check[level] = 0 // 부분집합 level(1~n) 이 없다는 뜻
DFS(level + 1)

6. DFS(1) 이 끝나면 answer 값을 반환하고 종료한다.

 

 

코드

<script>
  function solution(n) {
    let answer = [];
    let check = Array.from({ length: n + 1 }, () => 0); // [0, 0, 0, 0]
    function DFS(level) {
      if (level === n + 1) {
        let tmp = ""
        for (let i = 1; i <= n; i++) {
          if (check[i] === 1) tmp += `${i} `;
        }
        if (tmp.length > 0) answer.push(tmp.trim())
        console.log(check)
      } else {
        check[level] = 1;
        DFS(level + 1);
        check[level] = 0;
        DFS(level + 1);
      }
    }
    DFS(1);
    return answer;
  }

  console.log(solution(3));
</script>

 

소감:

꼭 복습하길

 

출처

자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의