[재귀함수] 재귀함수 기초 - 4 ( 부분집합 DFS )

자연수 1<=N<=10 주어짐

 

부분집합을 출력함

INPUT     : 3

OUTPUT : 

1 2 3

1 2

1 3

1

2 3

2

3

 

3의 모든 부분집합을 출력하는 것

 

DFS를 이용해서 풀어본다.

 

이건 그림을 그리면서 풀어주는게 point ~ 

---

핵심은 두갈래로 뻗는 것 !

1. 그림을 보면  DFS를 두개씩 O , X가 있는 부분을 볼 수 있음

 다 두개씩 탐색

 

2. 첫번째로 돌때 1,2,3을 들어가서 arr 배열을 이용해서 1로 체크된 것만 String에 담아서 출력을 해 줌

3. 그러면 이제 다시 2로 와서 X인 경우 3은 배열로 0으로 체크가 됐으니 1로 체크만 된 값들 출력

-> 1 2 3 / 1 2 가 출력된 상태

4. 이제 2가 없는 경우를 출력 1,3 하고 1이 존재

-> 1 2 3 / 1 2 / 1 3 / 1 출력된 상태

5. 다시 올라와서 이번엔 1이 없는 상태를 돈다

6. 1이 없으면서 2가 있는 상태를 돈다

-> 1 2 3 / 1 2 / 1 3 / 1 / 2 3 / 2 출력

7. 마지막으로 1이 없으면서 2도 없는 상태를 돔 

-> 3 , { } ( 다 0이므로 출력 X 문제에서 공집합은 출력한다고 하지 않았음)

 

 

package TreeDFS;

public class TreeDFS2 {
    static int n;
    static int[] arr; // 부분 집합을 사용한다,안한다 Boolean 이라고 생각하면 됨

    // 1. 재귀함수 만들어줌.
    public void DFS(int L){
        if(L == n+1){
            String tmp = "";
            for(int i=1; i<=n; i++){
                if(arr[i] == 1){ // 체크가 된 상태만 출력해준다.
                    tmp += (i + " ");
                }
            }
            System.out.println(tmp); // 담아서 출력 또는 출력하면서 줄바꿈 해도 OK
        }else{
            arr[L] = 1;
            DFS(L + 1); // 2. 사용한다.       1
            arr[L] = 0;
            DFS(L + 1); // 3. 사용하지 않는다. 0
        }
    }

    public static void main(String[] args) {
        TreeDFS2 tdf = new TreeDFS2();
        n = 3;
        arr = new int[n+1];
        tdf.DFS(1);
    }
}