DFS 주어진 수 부분집합 구하기

주어진 수를 DFS를 활용하여 부분집합을 구해보자

입력은 3이고, 3의 부분집합을 구하자

공식에 의하면 2^n 부분집합의 개수이다. 입력이 3이면 8이 부분집합의 개수이지만, 8개에는 공집합이 포함되어 있어 2^n -1 이 구현할 수 있는 부분집합의 개수이다.

그렇다면 DFS로 어떻게 부분집합을 구할까? 우선 DFS를 제일 작은 숫자인 1로 시작해야한다.

1로 시작해서 DFS(n+1)을 트리처럼 분기하여 2번 이어간다. 2번 이어가는 이유는 하나는 포함되고 하나는 포함되지 않는 상황을 만들기 위해서이다.

또한 왼쪽 자식노드는 포함시키고 오른쪽 자식노드는 포함시키지 않은 상황을 만들기위해 입력값+1만큼의 배열을 만들어 포함시킬지 여부를 만든다

int[] check = new int[input+1]

0을 제외하고 입력값의 크기만큼 배열을 만든다. 왼쪽노드를 지나가면 배열의 값을 1로 지정하고, 왼쪽 노드를 나와 오른쪽 노드를 갈 상황이 되면 0으로 만든다.

이 과정에서 왼쪽 노드를 나오게 되면 배열에 있는 모든 수를 출력하면 된다.

말로는 이해가 안갈테니 그림을 보자

DFS(1)을 시작으로 DFS(2) 두개로 나뉘고, 각D(2)는 +1한 D(3)으로 두개씩 나뉜다. 트리로 계속 증가하며 분기하다보면 입력값보다 +1인 값이 나온다.

조건문을 통해 입력값보다 +1인 값일 땐, 배열에 1인 인덱스를 모두 출력한다.

그래도 이해가 안갈테니 코드로 이해하자

public class Main {
    static int n;
    static int[] ch;

    public static void main(String[] args) {
        Main T = new Main();
        n = 3;
        ch = new int[n + 1];
        T.DFS(1);
    }

    public void DFS(int L) {
        if (L == n + 1) {
            for (int i = 0; i < ch.length; i++) {
                if (ch[i] == 1) {
                    System.out.print(i+" ");
                }
            }
            System.out.println();
        } else {
            ch[L] = 1;
            DFS(L + 1);
            ch[L] = 0;
            DFS(L + 1);
        }
    }
}
/* output
1 2 3 
1 2 
1 3 
1 
2 3 
2 
3
*/

메인 메소드에서 인스턴스 변수인 목표값과 배열의 크기를 지정해준다. 그렇게 1부터 DFS 순회를 시작한다

처음에 1이 들어가면 위에 그림처럼 DFS(2) DFS(2)로 나뉘는데, 이때 첫번째 자식(왼쪽)노드를 순회하기 전의 값을 배열에서 1로 만들어 포함시킬지 여부를 결정한다. 그렇게 왼쪽노드를 계속해서 따라가다보면 n 인 3보다 큰 4가 나오는데, 여기서 배열에 있는 값을 다 출력한다.

처음 4에 도달했을땐, 모든 원소가 1인 상태이므로 [1,2,3] 이 나온다. 그 다음 리턴되면 ch[L]=0을 만나고 다시 DFS(L+1)에 들어간다. L+1이 4인 상태이므로 또 출력하게 될텐데, 방금 전 L이 3인 상태에서 ch[L]=0 을 했으니 출력하면 2번째 출력문인 [1,2]이 나온다.

이렇게 순회를 따라가다보면 저렇게 답이 나온다.

저것이 공집합을 제외한 모든 부분집합이다. 개수는 2^n -1