[알고리즘] 7-6 부분집합 구하기 - DFS(깊이우선탐색) (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이 코드를 정리하고 있습니다.

• 문제 설명 : 자연수 n이 입력되면 1~n까지의 원소를 갖는 집합의 부분집합을 출력하는 문제(단, 공집합은 제외)

풀이

{1, 2, 3} 3개의 원소로 이루어진 집합의 부분 집합의 개수를 구하는 방법은

• 원소 1이 있는경우, 없는 경우 -> 2가지
• 원소 2가 있는 경우, 없는 경우 -> 2가지
• 원소 3이 있는 경우, 없는 경우 -> 2가지

2 * 2 * 2 = 8 로 8개의 부분집합을 가지게 된다.

(즉, n개의 원소를 가진 집합의 부분 집합의 개수는 2ⁿ)

집합의 각 원소를 트리의 노드로, 부분 집합에 포함된다 안된다를 간선으로 표현해 이진트리를 만들어보면 DFS(깊이 우선 탐색)을 진행하여 전체 부분집합을 구할 수 있다는 것을 알 수 있다.

코드

• boolean형 checked 배열을 만들고 각 인덱스를 집합의 각 원소로하여, 탐색 과정에서 해당 원소를 포함하는지를 표현
• 노드의 값이 n+1이라면 집합의 마지막 원소까지의 포함 여부 탐색이 끝난 것이다. 즉 하나의 부분집합을 찾아낸 것이다. checked 된 원소(인덱스)들을 출력한다.

package inflearn.recursive_tree_graph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//부분집합 구하기(DFS)
public class Main7_6 {

    static int n;
    static boolean[] checked; 

    public static void dfs(int L) {
        if (L == n + 1) {
            StringBuilder sb = new StringBuilder();
            for (int i = 1; i <= n; i++) {
                if (checked[i]) sb.append(i + " ");
            }

            if (sb.length() > 0) //공집합 제외
                System.out.println(sb.toString());
        } else {
            checked[L] = true; //원소 L을 포함하는 부분집합
            dfs(L + 1);
            checked[L] = false; //원소 L을 포함하지 않는 부분집합
            dfs(L+1);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        checked = new boolean[n+1]; //숫자 그대로를 인덱스로 사용하기위해 +1

        dfs(1);

        br.close();
    }
}