부분집합 구하기 (DFS)

설명

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

 

입력

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

 

출력

첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다.

단 공집합은 출력하지 않습니다.

 

예시 입력 1 

3

 

예시 출력 1

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

 

문제 해결

 

부분집합을 출력하는 문제이다.

1 2 3 이 있으면 1을 2를 3을 부분집합에 넣을 수도 있고, 안 넣을 수도 있다.=> 각각 경우의 수가 2가지 (즉 2의 n제곱)

예제 입력 3은 2의 3제곱 8개인데 공집합을 제외하니 7개의 부분집합이 나온다.

 

static int[] ch;

 

사용 여부를 체크할 체크 배열을 N+1 크기로 선언해준다.

 

• DFS(1)이 호출되고, 첫 번째 숫자(1)를 부분집합에 포함시키는 경우와 포함시키지 않는 경우를 탐색한다.
• 스택에 DFS 호출들이 쌓이며, 각 단계에서 숫자를 부분집합에 추가하거나 제외하는 선택을 하는 것이다.

 

 

• DFS(4)에 도달하면 if문이 참이 된다. 모든 선택이 완료됐고 (포함 or 미포함) 이 시점에서 ch 배열을 확인하여 부분집합을 결정한다.
• 위 그림에서는 DFS(3)에서 3을 포함하고 4를 제외한 경우이다.이 경우 부분집합은 {1, 2, 3}이 된다.

 

 

• 모든 숫자에 대한 선택이 완료된 후, 부분집합이 출력된다. 예를 들어 DFS(4) 호출이 종료되면, 출력에 해당하는 부분집합이 결정되는 것이다.

 

 

• 각 숫자에 대한 포함/미포함을 결정한 후 ch 배열을 이용해 실제 부분집합을 구성한다. 이후 DFS 함수가 호출되고, 스택에서 해당 함수 호출이 제거된다. (pop).
• 이 과정을 모든 가능한 부분집합을 탐색할 때까지 반복하면 된다.

 

최종 코드

 

import java.util.Scanner;

public class P06_부분집합구하기_DFS {
    static int N;
    static int[] ch;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        ch = new int[N+1];
        DFS(1);
    }

    public static void DFS(int L) {
        if (L == N + 1) {
            String tmp = "";
            for (int i = 1; i <= N; i++){
                if(ch[i] == 1) tmp += (i+" "); //i이면 체크됨
            }
            if(tmp.length() > 0) //공집합은 제외
                 System.out.println(tmp);
        } else {
            ch[L] = 1; //체크 배열 = 1 (사용 O)
            DFS(L + 1); //왼
            ch[L] = 0; //체크 배열 = 0 (사용 X)
            DFS(L + 1); //오
        }
    }
}