자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(DFS_부분집합 구하기)

 

 

 

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

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

예시 입력 1 

3

예시 출력 1

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

 

 

3은 1,2,3이 집합의 원소입니다.

부분집합은 2의 3제곱해서 8개 인데, 공집합 배니까 7개만 출력됩니다.

 

이진 트리로 2 갈래로 뽑는 상태 트리를 만들면 됩니다.

어떤 상태를 표현하는 트리를 상태 트리라고 합니다.

 

{1,2,3} 집합이 있을때  원소를 뽑아내서 부분집합을 만들어 내려고 할때,

1을 넣을 수도 있고 넣지 않을 수도 있습니다.

2를 넣을 수도 있고 넣지 않을 수도 있습니다.

3을 넣을 수도 있고 넣지 않을 수도 있습니다.

숫자 하나 당 2가지 경우가 존재합니다. 이렇게 곱하면 총 8가지입니다.

 

원소가 n개인 집합의 개수는 2의 n제곱이다. - 공집합도 포함됨

이런 원리로 하면 됩니다.

 

D(1)은 원소 1이라고 생각하면 됩니다.

내가 만들고자 하는 부분집합에 사용한다, 사용하지 않는다로 이진트리를 뻗어 나가면 됩니다.

종착지점인 4를 만날 경우 종료지점이라고 하면 하면, 1,2,3을 사용하는 거라고 생각하면 됩니다.

스택에 1,2,3,4가 들어가는데 4를 바로 pop 해버립니다. 그 후에 back해서 D(3)으로 오게 됩니다.

그러면 또 안했던 x가지의 D(4)로 가게 되서 다시 종료 지점이 됩니다.

 

 

D(L)은 레벨값을 의미하기도 하고 원소라고 생각하면 됩니다.

L = n+1일 경우에는 종료 지점이 되는 것입니다.

public class Main {

    static int n; // 집합의 원소의 개수
    static int[] ch; // 체크 배열 : 체크하고 안하고 하면서, 부분집합으로 할지 안할지 판단
    public void DFS(int L) {
        // 종착점에 왔을때
        if(L == n+1) {
            String tmp = ""; // 부분집합 표시용
            for (int i = 1; i <= n; i++) {
                // ch배열의 값이 1로 체크되었다면 출력
                if(ch[i] == 1) tmp+= (i+" ");
            }
            // 공집합일때는 출력안하기 위해 - 0이면 공집합
            if (tmp.length()> 0) System.out.println(tmp);
        // 종착점에 오지 않았을때는 2갈래로 뻗어나가기
        } else {
            ch[L] = 1;
            DFS(L+1); // 왼쪽(사용한다)
            ch[L] = 0;
            DFS(L+1); // 오른쪽(사용안한다)
        }
    }
    public static void main(String[] args) {
        Main T = new Main();
        n = 3;
        // 체크배열의 인덱스 번호를 원소라고 생각
		// 1부터 3까지 생기고 인덱스 0은 무시
        ch = new int[n+1];
        T.DFS(1);
    }
}

 

DFS(4)가 스택 프레임에 쌓이면 조건문에서 참이 됩니다.

ch라는 배열을 1부터 3까지 탐색하면서 1로 체크되어있는 인덱스 번호를 출력해주면 됩니다.