Algorithm - Find Subset ( DFS )
- 2023-12-21 에 풀이한 문제
- 문제 풀이 시간 : 0920 ~ 0935 ( 풀이 성공 )
- 나의 풀이 깃허브 : 풀이 클릭!
알고리즘 문제(Java) : 부분집합 구하기 ( DFS )
1. 문제
자연수 N이 주어지면, 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요.
2. 입력
- 첫 줄은 총 항수 N(1<=N<=10)이 주어집니다.
3. 출력
- 첫 줄부터 각 줄에 하나씩 공집합을 제외한 부분집합을 출력합니다.
4. 문제 풀이
- int[] ch 를 통하여 0 과 1을 넣어 중복값이 없도록 체크합니다.
- ch[L] = 1 이후 DFS(L+1) 을 하는건 아직 표시하지 않은 부분집합 루트이며 ( 1, 2, 3 … ),
- ch[L] = 0 이후 DFS(L+1) 을 하는건 이미 부분집합으로 채워진 부분이다. ( 1, 3 … 이미 1, 2, 3이 있어서 2는 스킵)
public class Find_Subset_DFS {
static int n;
static int[] ch;
public static void DFS(int L) {
if ( L == n+1 ) {
StringBuilder str = new StringBuilder();
for (int i=1; i<=n; i++ ) {
if ( ch[i] == 1 ) str.append(i).append(" ");
}
System.out.println(str);
return;
}
else {
ch[L] = 1;
DFS(L+1);
ch[L] = 0;
DFS(L+1);
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
ch = new int[n+1];
DFS(1);
}
}