#include <iostream>
int n, ch[11];
void DFS(int L){
int i;
if(L==n+1){
for(i = 1; i <= n; i++){
if(ch[i] == 1) printf("%d ",i);
}
puts("");
}
else{
ch[L] = 1;
DFS(L+1);
ch[L] = 0;
DFS(L+1);
}
}
using namespace std;
int main() {
scanf("%d",&n);
DFS(1);//1레벨부터
return 0;
}
모든 부분집합을 출력하는 문제는 곧 모든 경우의 수를 찾아야하는 문제이다. 따라서, DFS로 해결가능한 문제라는 것이다.
(물론 꼭 DFS로만 풀 수 있다는 것이 아니라 "가능"하다는 것이다.)
DFS는 재귀를 이용하기 때문에 Stack Frame에 함수가 하나하나씩 쌓이며, 쌓여있는 함수는 각자의 역할을 끝내면 Frame에서 사라지게 된다.
그리고 각 함수들은 자신들의 역할이 있으며 자신의 역할이 끝나면 복귀주소로 되돌아간다.(복귀주소는 STACK FRAME에 쌓여있던 이전 함수이다. 즉, 부모 노드이다)
DFS는 각 함수가 어떤 역할을 해야하는지 잘 결정해주어야하고, 언제 더이상 자식가지를 안만들지 혹은 완전히 끝내버릴지 잘 결정해야한다.
아래는 DFS트리와 과정이다.
D(1)으로 시작하며, 각 함수들은 L매개변수를 ch배열에 체크하느냐 안하느냐로 나뉘어 왼쪽가지 오른쪽 가지로 뻗어나간다.
이를 통해 부분집합에 대한 모든 경우의 수를 알아낼 수 있다.
그리고 D(4)에서 출력하여 더이상 가지가 뻗어나가지 않고 Stack Frame에서 삭제되어 그 다음 Stack Frame을 실행하게 된다.
참고로, 위의 D(3)...1 2 3과 D(3)...1 2는 트리에서 맨 왼쪽 하단의 함수로써, 서로 같은 함수이다. 따라서 STACK FRAME에 저렇게 표기하는건 올바르지 않다. D(3)...1 2 3을 마치고 D(4)...출력을 한다음 D(4)가 STACK FRAME에서 삭제되어, D(3)... 1 2를 실행한다고 생각해야 한다. 내가 표기한 STACK FRAME은 단지 함수 실행 순서가 저렇다라고만 이해해야 한다.
