section7.6

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

입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.

출력설명
첫 번째 줄부터 각줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다.
단 공집합은 출력하지 않습니다.

입력예제 1
3

출력예제 1
1 2 3
1 2
1 3
1
2 3
2
3

 

 

 

ANSWER

public class Question6 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
    }

    public void DFS(int n) {
        /*
                   1
              2          3
        - 이걸 어떻게 DFS로 풀지 ,,,?

        방법1. 부모노드 > 1. 자기 자신 출력
                      > 2. 자기 자신 + 오른쪽 노드 출력
                      > 3. 자기 자신 + 왼쪽 노드 출력
                      > 4. 자기 자신 + 오른쪽 노드 + 왼쪽 노드 출력
                      > 아래로 내려감 > 다시 부모노드
                      >> 4 5 추가 되면 안됨
                      >> 2 3 이런 부분 집합은 출력 불가함
         방법2. ...
               DFS를 사용하지 않는다면 이중 for 문을 돌려서 부분집합 구할 수 있을 것 같음
        */
    }
}

• 어쨌든 DFS 문제니까 최대한 이진트리를 만들어서 풀어보려고 했다

              (start)
                {1}
          /            \ 
        {2}            {3}

• 내가 생각했던 이진트리는 단지 숫자를 나열하는 것이었고 전체를 탐색하자는 생각이었는데 불가능했다
• 새로운 알고리즘이 나오면 빠르게 포기하고 어떻게 푸는지 방식을 보는 게 더 중요하다 생각해서 포기했다

 

 

 

SOLUTION

public class Answer6 {
    static int n;
    static int[] ch; // 체크배열(부분집합 사용한다/안한다)
    public void DFS(int L) {
        if (L == n+1) {
            // 종착점 도착
            String tmp = "";
            for (int i = 1; i < n; i++) {
                if (ch[i] == 1) {
                    tmp += (i + " ");
                }
                if (tmp.length() > 0) {
                    System.out.println(tmp);
                }
            }
        } else {
            ch[L] = 1;
            DFS(L+1); // 왼쪽(사용한다)
            ch[L] = 0;
            DFS(L+1); // 오른쪽
        }

    }

    public static void main(String[] args) {
        Answer6 T = new Answer6();
        n = 3;
        ch = new int[n+1]; // 체크배열의 인덱스를 원소로 사용
        T.DFS(n);
    }
}

 

                    (start)
                       {}
         O(1) /                 \ X(1)
           {1}                   {}
   O(2) /      \ X(2)    O(2) /      \ X(2)
   {1,2}        {1}       {2}          {}

• 내가 생각했던 것과 다르게 존재 유무를 가지고 이진트리를 만들어 푸는 것이었다
• 아직도 적응 안되는 DFS,,, 스택을 쌓아서 하나씩 재귀 호출하고 참 어렵다
• 익숙해지겠지?