[Algorithm] DFS(부분집합 구하기)

설명

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

 

입력

3

 

출력

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

 

풀이.

public class Main {
    static int n; // 입력받을 값 , 전역변수 선언
    static int[] ch; // 출력해야할 값들을 체크해줄 배열 , 전역변수 선언 (1 or 0으로 비교할 것)
    public void DFS(int L){
        if(L == n+1){ // DFS함수의 인자값 L이 입력값 n보다 크면 종료 시점은 참이된다.
            for(int i=0; i<=n; i++){
                if(ch[i]==1) System.out.printf(i+" ");
            }
            System.out.println();
        }else{
            ch[L] = 1; // 배열의 (현재 들어온 인자)인덱스를 1으로 만들고 ..
            DFS(L+1); // 왼쪽라인을 태운다.
            // ------------------------------------------------------ //
            ch[L] = 0; // 배열의 (현재 들어온 인자)인덱스를 0으로 만들고 ..
            DFS(L+1); // 오른쪽라인을 태운다.
        }
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 입력받은 값
        ch = new int[n+1]; // 입력받은 값 만큼 배열 크기 초기화
        T.DFS(1);
    }
}

 

---

 

정리 :

1. 아래로 뻗어 나가는 이진트리 구조를 생각한다.

2. 위 문제에서는 트리의 노드를 구상할 때 왼쪽자식(현재 L값을 출력한다) , 오른쪽자식(현재 L값을 출력하지 않는다) 로 나누었다.

3. 출력여부는 ch라는 배열을 초기화하여 출력할 왼쪽노드는 1과 하지않을 오른쪽노드에는 0을 넣어서 사용 하였다.

4. 트리가 뻗어나가면서 호출되고 소멸되는 스택프레임 구조를 순서대로 손으로 그리고 지워가는 연습이 필요하다.