✏️ 문제

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

입력설명
첫 번째 줄에 자연수 N(1 ≤ N ≤ 10)이 주어집니다.

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

입력 예제

1
3;

출력 예제

1
2
3
4
5
6
7
1 2 3
1 2
1 3
1
2 3
2
3

👉 부분 집합을 구하는 문제

1을 방문을 할 지 안 할지 2가지 선택, 2를 방문을 할 지 안 할지 2가지 선택, 3을 방문을 할 지 안 할지 2가지 선택
➡️ 총 8가지의 트리가 만들어진다.

1
2
3
4
5
6
7
8
9
10
11
12
13
상태트리

부분집합의 개수 2 ^ x - 1 (공집합 제외)
집합에 원소가 들어갈지 안들어갈지 선택한다.

D(1) -> O -> D(2) -> o -> D(3) -> o
                               -> x
                  -> x -> D(3) -> o
                               -> x
     -> X -> D(2) -> o -> D(3) -> o
                               -> x
                  -> x -> D(3) -> o
                               -> x

문제에서 1부터 N까지의 원소를 갖는 부분집합을 구하라고 했기 때문에, 1부터 N까지의 길이에 0을 담은 체크 배열을 만들어준다.

1
let checkArray = Array.from({ length: n + 1 }, () => 0);

이제 Head 노드에서부터 노드를 방문하면서, 해당 노드를 포함할 것인지 확인하고, 부분 집합을 찾아준다.

(내가 만든 부분 집합에 참여시키고 참여시키지않는 것을 확인 후 배열에 하나씩 담아주면 된다.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function DFS(depth) {
  if (depth === n + 1) {
    let temp = '';
    for (let i = 1; i <= n; i++) {
      // 1로 들어온 것들만 출력하기
      if (checkArray[i] === 1) temp += i + ' ';
    }
    if (temp.length >= 1) answer.push(temp.trim());
  } else {
    // 집합에 포함시킨다.
    checkArray[depth] = 1;
    DFS(depth + 1);
    // 집합에 포함시키지 않는다.
    checkArray[depth] = 0;
    DFS(depth + 1);
  }
}

👉  DFS 함수를 잘 살펴보자

  1. 부분집합이 주어진 배열의 길이를 넘어갈 수는 없으므로, depth가 배열의 길이와 같다면 재귀를 멈추고, 1로 들어온 인덱스만 출력한다.
  2. depth가 아직 배열의 길이에 도달하지 않으면, 자기 자식 노드를 선택하는 경우와 그렇지 않은 경우를 만들고, 자식을 호출하여 부분집합을 찾아간다.

✅ 전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function solution(n) {
  let answer = [];
  let checkArray = Array.from({ length: n + 1 }, () => 0);

  function DFS(depth) {
    if (depth === n + 1) {
      let temp = '';
      for (let i = 1; i <= n; i++) {
        // 1로 들어온 것들만 출력하기
        if (checkArray[i] === 1) temp += i + ' ';
      }
      if (temp.length >= 1) answer.push(temp.trim());
    } else {
      // 집합에 포함시킨다.
      checkArray[depth] = 1;
      DFS(depth + 1);
      // 집합에 포함시키지 않는다.
      checkArray[depth] = 0;
      DFS(depth + 1);
    }
  }

  DFS(1); // DFS는 1부터 시작한다.
  return answer;
}

😎 Review

DFS를 사용하려면 재귀함수가 기본적인 지식으로 깔려 있어야하는 것 같다. 재귀함수를 배웠다고 생각했는데 막상 그것도 아닌가보다. 😟 DFS가 실행되는 과정에 대해서 더 이해하는 과정이 필요할 것 같다. 부분집합을 구하라는 문제를 봤을 때, 어떻게 구해야하지 라고 생각하다가 가지치기 형식으로 그림을 그리다보니 이진트리 형태로 나오는 것을 보면서 이러면 이진트리로 접근해야겠다. 라는 생각이 들었던 것만으로도 오늘은 성공인것 같다!