728x90
부분 집합 구하기(DFS)
이번 시간에는 DFS 를 이용한 부분 집합을 구하는 방법에 대해서 배워보자.
문제
자연수 N 이 주어지면 1 ~ N 까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요.
단, 공집합은 출력 하지 않습니다.
입력
3
출력
1 2 3
1 2
1 3
1
2 3
2
3
$$원소의 개수가 N 인 부분집합의 개수 : 2^n$$
$$공집합을 제외한 부분집합의 개수 : 2^n-1$$
루트 노드부터 보면, 1을 포함하는 경우 하지 않는 경우로 나누고, 2 depth 에서는 원소 2를 포함하는 경우 하지 않는 경우로 나눌 수 있다. 따라서, N 만큼의 반복을 돌고 depth 가 N + 1 이 되는 경우 종료된다.
구현
public class Main {
private static int N;
private static boolean[] checked; // checked 배열 : 해당 숫자를 부분집합으로 사용하는지 안하는지 판단하기 위함
public static void main(String[] args) {
input();
dfs(1);
}
private static void input() {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
checked = new boolean[N + 1];
}
/**
* @param L 각 뎁스에 해당하는 숫자를 의미 N 이 3이면 L 은 1 ~ 4 까지의 DEPTH 를 가진다.
*/
private static void dfs(int L) {
if(L == N + 1) { // 종료 조건을 만나면 checked 의 원소가 true 인 애들을 출력
StringBuilder stringBuilder = new StringBuilder();
for (int i = 1; i <= N; i++) {
if(checked[i]) {
stringBuilder.append(i).append(" ");
}
}
if(stringBuilder.length() > 0) { // 공집합 출력 X
System.out.println(stringBuilder);
}
// check 배열에 있는 true 로 체크되어있는 원소를 출력
} else {
checked[L] = true; // L 이라는 원소를 사용한다라는 의미
dfs(L + 1); // 왼쪽으로 뻗는 그래프
checked[L] = false; // L 이라는 원소를 사용하지 않는다라는 의미
dfs(L + 1); // 오른쪽으로 뻗는 그래프
}
}
}
728x90
'Algorithms > 기본 지식' 카테고리의 다른 글
LIS(최장 증가 부분 수열) (0) | 2022.01.11 |
---|---|
조합(Combination) (0) | 2022.01.03 |
깊이 우선 탐색(DFS) (0) | 2022.01.03 |
위상 정렬 (0) | 2021.12.14 |
신장 트리와 크루스칼 알고리즘 (0) | 2021.12.13 |