[JAVA] DFS - 부분 집합 구하기

문제 

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

 

N을 선언하고, 부분집합으로 사용하는지 안하는지 체크하는 check 배열을 n+1크기로 만든다.

 

ex. N=3

T.DFS(1) 1부터의 원소를 DFS

n+1은 4이고, L은 1이기 때문에 else 문 수행

ch[1]에 1을 체크해준다. 1 0 0 -> DFS(2) 수행하고 DFS(1) 함수가 끝나지 않았기 때문에 리턴 주소를 스택 프레임에 push

 

L이 2이기 때문에 else문 수행

ch[2]에 1 체크 1 1 0 -> DFS(3) 수행 -> stack.push(DFS(2))

 

L = 3 else 문 수행

ch 1 1 1 -> DFS(4) -> stack.push(DFS(3))

 

L = 4 if문 수행

1부터 n까지의 ch 배열에서 사용 가능한 1들을 출력(공집합은 출력하지 않는다) -> 1 2 3

 

스택 프레임을 pop하면 맨 위의 DFS[3]의 리턴 주소로 돌아간다.

ch[L] = 0;

DFS(L+1);

ch[3] = 0 -> 1 1 0 -> DFS(4) -> if문 수행 -> 1 2 출력 -> stack.pop = DFS(2)

 

ch[2] = 0 -> 1 0 0 -> DFS(3) -> ch[3]=1 -> 1 3 출력 

...

이렇게 나온 결과들은 1~N까지의 원소를 갖는 집합의 부분집합을 모두 출력할 수 있다.

public class Solution {
    static int n;
    static int[] ch; // check 배열 : 부분집합으로 사용할지 안할지 체크
    public void DFS(int L){
        if(L==n+1){
            String temp = "";
            for(int i=1; i<=n; i++){
                if(ch[i]==1) temp+=(i+" "); // check
            }
            
            if(temp.length()>0) System.out.println(temp); // 공집합 출력 X

        } else {
            ch[L] = 1; // 사용 O
            DFS(L+1); // 왼쪽 = 사용
            ch[L] = 0; // 사용 X
            DFS(L+1); // 오른쪽 = 사용 X
        }
    }
    public static void main(String[] args) {
        Solution T = new Solution();
        n = 3;
        ch = new int[n+1];
        T.DFS(1);
    }
}