[자료구조] 부분 집합 구하기 (DFS)

 

부분집합 구하기

• A 집합의 원소가 n개라고 가정 했을 때 A 집합의 부분 집합 총 개수는  2ⁿ개다. (공집합 포함)

 

🔍 원리

• 집합의 원소가 {1, 2, 3}라고 가정할 때 모든 부분 집합을 구하는 것이다.
• 원소 하나 하나가 포함하는지, 미포함하는지 정해야한다.
• 예를 들어서 원소가 1~n 까지의 자연수라고 할 때 DFS(n+1) 까지의 함수를 호출해서 DFS(n+1) 일 때, 요소를 다 출력하고 함수를 빠져나오도록 작성한다.

 

 

 

🔍 부분 집합 구하기 코드로 구현

public class Prac {
	
	static int n;
	static boolean[] check;  // 해당 값을 포함하면 true, 아니면 fasle으로 체크해주기 위한 배열
	static StringBuilder sb;
	
    public static void main(String[] args) {
    	n=3;
    	check = new boolean[n+1];  // 0번째 인덱스 사용 안하기 위해 n+1 만큼 크기 잡음
    	DFS(1);  // 1~3 까지의 부분집합을 구하기 위해 파라미터값이 1부터 시작
   }
    
   static void DFS(int L) {
	   if(L == n+1) { 
		   sb = new StringBuilder();
		   for(int i=1; i<=n; i++) {
			   if(check[i]) sb.append(i);
		   }
		   if(sb.length()>0) System.out.println(sb.toString());
		   return;
	   }
	   
	   check[L]=true;
	   DFS(L+1);  // 자식 노드의 왼쪽으로 진행
	   check[L]=false;
	   DFS(L+1);  // 자식 노드의 오른쪽으로 진행
	   
   }
   
}

123
12
13
1
23
2
3

• 집합의 원소가 1~n 까지의 자연수라고 가정할 때, 공집합을 제외한 모든 부분 집합 구하기. 
• 대부분의 DFS 재귀함수는 if-else 문으로 구현할 수 있다.

 

 

---

 

🔍 0~3까지의 자연수들을 원소를 가지는 집합의 부분 집합 구하기

public class Prac {
	
	static int n;
	static boolean[] check;  // 해당 값을 포함하면 true, 아니면 fasle으로 체크해주기 위한 배열
	static StringBuilder sb;
	
    public static void main(String[] args) {
    	n=3;
    	check = new boolean[n];  // 0번째 인덱스 사용 안하기 위해 n 만큼 크기 잡음
    	DFS(0);  // 1~3 까지의 부분집합을 구하기 위해 파라미터값이 1부터 시작
   }
    
   static void DFS(int L) {
	   if(L == n) { 
		   sb = new StringBuilder();
		   for(int i=0; i<n; i++) {
			   if(check[i]) sb.append(i);
		   }
		   if(sb.length()>0) System.out.println(sb.toString());
		   return;
	   }
	   
	   check[L]=true;
	   DFS(L+1);  // 자식 노드의 왼쪽으로 진행
	   check[L]=false;
	   DFS(L+1);  // 자식 노드의 오른쪽으로 진행
	   
   }
   
}

012
01
02
0
12
1
2