6. 부분 집합 구하기(DFS)

1. 문제

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

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

 

입력

3

 

출력

1 2 3

1 2

1 3

1

2 3

2

3

 

2. 나의 풀이

도통 모르겠어서 강의 봄

 

 

3 - 1. 강의 풀이

D(1)부터 시작해서

왼쪽 트리는 D(num)의 num을 사용하는 트리 

오른쪽 트리는 D(num)의 num을 사용하지 않는 트리

사용함과 사용하지 않음은 int[n+1] 만큼의 배열에 표시한다. 

 

 

1부터 3까지의 부분 집합을 출력하고자 하면

DFS는 (3+1) 즉 4까지 생성하고 num이 4이면

for(int i = 1 ; i<=3 ;i++) 까지 int 배열에 값이 1인 인덱스만 출력한다.

 

코드를 보면 이해가 빠르다.

 

 

3 - 2. 강의 코드

package BFS_DFS;
import java.util.*;

public class dfs06 {
    static int[] ch;
    static int n;

    public static void DFS(int num) {
    	//DFS가 n+1까지 생성되면 ch에 표시한 사용 여부 숫자를 출력한다.
        if (num == n + 1) {
            String tmp = "";
            for (int i = 1; i <= 3; i++) {
                if(ch[i] == 1) tmp += (i + " ");
            }
            if(tmp.length() >0) System.out.println(tmp);
            //공집합이면 tmp에 아무것도 추가되지 않아 tmp.length()가 0이므로 출력되지 않음.
        } 
        else {
            ch[num] = 1; //num을 사용한다는 표시를 하고 다음 DFS
            DFS(num+1);
            ch[num] = 0; //num을 사용하지 않는다는 표시를 하고 다음 DFS
            DFS(num+1);         
        }
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = 3;
        ch = new int[n + 1];
        
        DFS(1);
    }
}

 

4. 얻어 갈 점.

DFS부분은 이론은 이해가 되는게 문제에 어떻게 사용해야 할 지는 감이 오지 않는다.

많은 문제를 풀어보자