[Ch.07 - DFS] 02. 부분집합 구하기

2. 부분집합 구하기

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

입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
출력설명
첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다. 
단 공집합은 출력하지 않습니다.

입력예제 1 

3

출력예제 1

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

 

1. 이진트리를 사용하는 이유 -> 부분집합이 존재하는지 존재하지 않는지로 구분되기 때문에
   
   1. L==n+1일 경우
      1. 부분집합 체크 배열 생성
      2. 임시변수에 부분집합인 경우만 저장
   2. L==n+1이 아닌 경우
      1. 부분집합 체크 배열에 해당여부 체크
      2. 왼쪽 자식 -> 부분집합 해당
      3. 오른쪽 자식 -> 부분집합이 아님
2. DFS(1)을 넣어서 시작 -> 1부터 시작, ++해서 1이 n+1이 될때까지

 

---

package dfsbfs.ch07;

import java.util.Scanner;

//부분집합 구하기 (DFS)
//주어진 N을 이용해 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램
//공집합 출력하지 않는다.
//2n^-1 [공집합 제외]

public class Dfsbfs02 {
	// D(1) -> O / X로 부분집합이 될 때도, 안 될 때도 존재하므로, 이진트리 이용
	// D(1) -> D(2), D(2)
	// D(2) -> O / X
	// D(2) -> D(3), D(3)
	// D(3) -> O / X
	// D(4) -> D(4), D(4) -> D(L)에서 L==n+1은 단말 노드
	// D(1) -> O -> D(2) -> O -> D(3) -> O :1,2,3
	// D(1) -> O -> D(2) -> O -> D(3) -> X :1,2

	static int n;
	static int[] ch;

	// 체크를 하는 배열 -> 부분집합 사용 여부 확인
	public void DFS(int L) {
		// L이 1로 왔을 때 -> 부분 집합 사용 여부 체크

		if (L == n + 1) {
			String tmp = "";
			// 임시 변수 생성
			for (int i = 1; i <= n; i++) {
				if (ch[i] == 1) {
					tmp += (i + " "); // 자동형변환
				}
				//존재할때만 tmp에 넣어서 -> 공집합이 아닐때만 출력
			}
			if (tmp.length() > 0)
				System.out.println(tmp);
			// 공집합 아닌 경우에만 출력

		} else {
			ch[L] = 1; // O인 경우
			DFS(L + 1); // 왼쪽 자식 노드 -> O

			ch[L] = 0;
			DFS(L + 1); // 오른쪽 자식 노드 -> X
			// 종착점이 아닌 경우 두가지 경우로
		}
		// 종착점인 경우 L이 N+1일 때 -> 부분집합 경우의 수 생성
	}

	public static void main(String[] args) {
		Dfsbfs02 T = new Dfsbfs02();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		// n과 ch을 static으로 생성한 이유
		ch = new int[n + 1];
		// 체크 배열의 원소를 인덱스 번호로 하기 위해 -> 인덱스 번호가 1~3까지 생성
		T.DFS(1);
	}

	// 스택그리기 : D(1) -> L이 1이므로, 부분집합 사용 여부 확인 -> ch :[1,0,0]
	// D(2) -> ch : [1,1,0]
	// D(3) -> ch : [1,1,1]
	// D(4) -> L==n+1 -> 1로 체크되어있는 인덱스 배열 출력 : 1,2,3 출력 -> D(4) pop

	// D(3) -> ch[L]=0; ch :[1,1,0] -> D(4) -> L==n+1 -> 1로 체크되어있는 인덱스 배열 출력 : 1,2
	// 출력 -> D(4) pop
	// D(3) pop -> D(2) -> ch[L]=0; ch :[1,0,0]
	// -> D(3) -> ch[L]=1; ch:[1,0,1] -> D(4) -> L==n+1 -> 1로 체크되어있는 인덱스 배열 출력 : 1,3
	// 출력 -> D(4) pop

}