DFS - 부분집합 구하기

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

 

▣ 입력설명

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

 

▣ 출력설명

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

 

▣ 입력예제 1

3

 

▣ 출력예제 1

1 2 3 1 2 1 3 1 2 3 2 3

---

📝풀이과정

원소의 갯수가 n개일 때 부분집합의 갯수는 2^n이다.

예를 들어 1, 2, 3을 가지는 집합에서 부분집합의 갯수를 구하고자한다.

이 때 각 원소마다 원소를 가지는지 가지지 않는지 경우의 수가 2개 존재한다.

각 경우의 수가 원소마다 존재하기 때문에 2*2*2 = 2^3이 된다.

이것을 트리의 형태로 표현하면 다음과 같다.

 

즉, 1부터 DFS를 진행하여 해당 원소를 포함하는지 포함하지 않는지를 재귀로 구현할 수 있다.

이때 탐색을 완료했으면 부분집합이 완성된 것이다. 이것을 매 탐색마다 체크하기 위해서 체크 배열을 하나 생성한다.

체크배열의 갯수를 n+1로 지정한 이유는 인덱스 1부터 원소를 체크하기 위해서다.

 

탐색을 종료하는 조건은 DFS함수의 파라미터가 N+1이 되는 경우이다.

즉, 위의 예시에서 4가 된다면 탐색을 종료하고 지금까지 어떤 숫자들이 체크되었는지를 확인하면 된다.

처음 탐색을 마치면 체크배열에 인덱스1, 인덱스2, 인덱스3이 체크되어 있고, 따라서 answer 배열은 1, 2, 3이 들어간다.

그리고 3을 체크배열에서 포함하지 않을 것이라고 표시한다. 그리고 그 다음 탐색을 하면 answer 배열은 1, 2가 들어간다.

그 다음에는 2를 체크배열에 포함하지 않을 것이라 표시하고 그 다음 탐색을 반복한다.

🛠코드

function solution(n) {
  const result = [];
  const ch = Array.from({ length: n + 1 }, () => 0);
  function DFS(L) {
    if (L === n + 1) {
      let temp = '';
      for (let i = 1; i <= n; i++) {
        if (ch[i] === 1) temp += i + ' ';
      }
      if (temp.length > 0) result.push(temp);
    } else {
      ch[L] = 1;
      DFS(L + 1);
      ch[L] = 0;
      DFS(L + 1);
    }
  }
  DFS(1);
  return result.join('\n');
}

console.log(solution(3));

 

느낀점

상당히 어려웠다. 맨 처음에는 부분집합을 구하는 원리를 트리 형태로 그리지도 못했다.

또한 체크 배열을 활용한 새로운 접근 방법도 처음에는 생각하지 못했다.

코드를 보면 이해가 되지만 다시 풀어보았을 때 풀이법을 외워서 작성하지는 않을지 걱정된다.

재귀를 활용해서 트리의 순회를 구현한 문제와 비슷하지만 유형이 조금 바뀌니 전혀 다른 문제가 된 거 같다.

복습, 또 복습하자.