[PS] 인프런 강의 - Tree 2. 부분집합 구하기 (DFS)

 

문제

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

 

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

 

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

 

▣ 입력예제 1
3

 

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

풀이

n=3일 때 원소는 {1, 2, 3}이고, 원소를 '사용한다/안한다' 로 경우의 수가 2씩 잡힌다.

따라서 가질 수 있는 모든 부분집합의 경우의 수는  2x2x2 =8이다. 

경우의 수가 2씩 있으므로 자식노드가 2개씩 늘어나는 트리를 깊이 우선 탐색 하면 모든 경우의 수를 구할 수 있다.

 

우선 결과를 저장할 ch배열을 선언한다. 사용할 인덱스는 1~n 이다.

루트 1이 최초로 DFS 함수를 호출한다.

해당 숫자를 사용할 경우 왼쪽으로 내려가고 ch[ i ] 에 1을 저장한다.

사용하지 않을 경우 오른쪽으로 내려가고 ch[ i ] 에 0을 저장한다.

 

다음 그림은 n=3인 트리이고, n=4가 되면 ch 배열을 순회하며 값이 1인 인덱스(i) 만 출력하면 된다

코드

import java.util.Scanner;

public class Main {
	
	static int n;
	static int[] ch;
	
	public static void DFS(int L) {
		if(L == n+1) {
			String tmp="";
			for(int i=1; i<n+1; i++) {
				if(ch[i] == 1) tmp+=(i + " ");
			}
			if(tmp.length() > 0) System.out.println(tmp); //공집합은 출력X
		}
		else{
			ch[L] = 1;
			DFS(L+1); //left (사용)
			
			ch[L] = 0;
			DFS(L+1); //right (사용X)
		}
		
	}
	
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        n = in.nextInt(); //1~10
        //1~N 원소를 갖는 부분집합 모두 출력
        ch = new int[n+1]; //인덱스 1~n 
        DFS(1); //1부터 시작
        

    }
}