[인프런 코딩테스트] 이진트리(깊이 우선 탐색)로 부분집합 구하기, DFS

1. 문제

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

단, 공집합은 출력하지 않습니다. 

 

1) 부분집합과 공집합

우선 문제를 풀기 전에, 부분집합에 대해서 알아보자.

 

부분집합은 한 집합의 일부를 나타내는 것으로, 집합 A의 모든 원소가 집합 B에 포함될 때 A를 B의 부분 집합이라고 한다.

공집합은 원소를 하나도 가지고 있지 않은 집합으로, 부분집합에 포함된다. 

 

만일 { 1, 2, 3 }이라는 집합이 있다고 해보자.

이때 부분집합을 구하기 위해서는 각 원소들이 집합에 포함되는지 확인해야 한다.

 

1이 포함되는 경우와 그렇지 않은 경우, 2가 포함되는 경우와 그렇지 않은 경우, 3이 포함되는 경우와 그렇지 않은 경우.

이를 트리로 표현하면 위와 같으며, 총 8개의 부분집합이 나오게 된다.

 

 

2) 풀이 

function solution(n) {
    let answer = [];
    //1, 0으로 check(포함 할지 안할지)
    let ch = Array.from({ length: n + 1 }, () => { 0 })

    function DFS(v) {
        if (v === n + 1) {
            let tmp = ""
            for (let i = 1; i <= n; i++) {
                if (ch[i] === 1) tmp += i + ""
            }
            //공집합 제외 
            if (tmp.length > 0) answer.push(tmp.trim());
        } else {
            ch[v] = 1;

            DFS(v + 1);
            ch[v] = 0
            DFS(v + 1);
        }
    }
    DFS(1)
    return answer;
}
console.log(solution(3));

 

부분집합의 경우 해당 원소가 들어가거나 들어가지 않는, 두 가지 경우의 수로 나뉜다.

따라서 이를 판단해 트리로 만들어주면 된다. 

 

그리고 각각의 순회가 끝날 때, 부분집합이 완성되므로 해당 값을 출력해 주면 된다.

 

 

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

 

우선, 해당 원소가 들어가는지, 들어가지 않는지 체크할 체크배열을 만들어준다.

해당 체크 배열은 각각의 원소마다 체크해줘야 하므로 원소의 개수만큼 존재해야 한다.

 

단, 배열의 경우 인덱스가 0부터 시작하므로 n+1의 개수만큼 배열을 만들어준다.

(1, 2, 3의 값이 필요함)

 

그리고, 해당 값을 0으로 초기화해준다.

여기서 0은 해당 원소가 들어가지 않는 경우, 1은 들어가는 경우이다. 

 

즉, ch[1] = 0,  ch[2] = 0, ch[3] = 0 이 기본값이 된다. 

 

 

if (v === n + 1) {
  //종료조건         
} else {
 
}

 

그 후 종료조건을 적어준다.

 

우리는 N까지의 부분집합을 구하면 되기 때문에 v가 n+1의 값과 같을 때 순회를 멈춰준다.

그리고 종료 후에는 해당 집합을 출력해 주면 된다. 

 

 

 if (v === n + 1) {
  let tmp = ""
  for (let i = 1; i <= n; i++) {
    if (ch[i] === 1) tmp += i + ""
  }
  //공집합 제외 
  if (tmp.length > 0) answer.push(tmp.trim());



DFS가 종료된 후에는 해당 집합을 출력해줘야 한다.

집합에 포함되는 경우에만 출력해야 하기 때문에 for문을 통해 ch 배열에서 값이 1인 것들만 tmp에 넣어준다.

 

그리고 공집합은 제외해야 하므로 tmp.length가 0이면 trim()를 통해 공백을 제거해 준다.

 

 

else {
  ch[v] = 1;

  DFS(v + 1);
  ch[v] = 0
  DFS(v + 1);
}

 

이제 DFS 호출 부분을 살펴보자.

 

부분집합 트리는 원소가 포함되는 경우, 포함되지 않는 경우에 따라 양쪽으로 나뉜다.

따라서 맨 처음에 ch[v] = 1을 통해 해당 값이 포함되는 경우로 설정해 준다.

 

DFS(v+1)을 통해 DFS를 호출하면, v가 n+1이 될 때까지 DFS를 계속해서 호출하게 된다.

그리고 ch[v = 1]을 통해 해당 값이 포함되는 경우로 바뀐다.

 

//DFS(1)
ch[1] = 1;
DFS[1+1];

ch = [0, 1, 0, 0];

//DFS(2)
ch[2] = 1;
DFS[2+1];

ch = [0, 1, 1, 0];

//DFS(3)
ch[3] = 1;
DFS[3+1];

ch = [0, 1, 1, 1];

//DFS[4]
if(4 === 3+1) {
  ...
}

tmp = 123

 

answer가 출력되는 과정은 위와 같다.

v의 값이 n+1보다 커질 때까지 ch 배열에 있는 값을 모두 1로 바꿔주고, 맨 마지막에 값이 1인 것들의 index를 출력해 준다. 

 

//DFS(3)
ch[3] = 0;
DFS(3+1);

ch = [0, 1, 1, 0]

//DFS(4)
if(4 === 3+1) {...}

tmp = 12

 

DFS(4)가 if에 걸려 끝이 나면 이제 다음 단계로 넘어가게 된다.

그다음 줄인 ch[3] = 0으로 돌아와서 ch 값을 바꿔준다. 

(DFS(3)의 나머지 부분을 마저 진행한다.)

 

그 후 다시 n+1을 통해 DFS(4)를 호출하고, 이는 n+1의 값과 같으므로 종료조건에 걸려 출력된다. 

이때 호출스택에는 DFS(1), DFS(2)가 쌓여있는 상태이다. 

 

 

//DFS(2)
DFS(2) = 0;
DFS(2+1);

ch = [0, 1, 0, 0];


//DFS(3)
ch[3] = 1;
DFS(3+1);

ch = [0, 1, 0, 1];

//DFS(4)
if()...

tmp = 13

 

 

이제 DFS(2)의 나머지 코드를 실행해서 ch[2]의 값을 바꿔준다.

그 후 DFS(2)에서 호출된 DFS(3)이 다시 실행되고, ch[3]의 값이 1로 바뀌고, DFS(4)가 호출되면서 13이 출력된다. 

 

위 과정이 반복되면 최종적으로 123 12 13 1 23 2 3 이렇게 7개의 부분집합이 출력된다.