[c++] DFS를 이용한 부분집합

자연수 n이 주어지고 1부터 n까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하는 문제를 DFS를 사용해서 풀어보았다.

 

풀이 코드는 아래와 같다.

#include <stdio.h>
using namespace std;
int n, ch[100];
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);
	}
}	
int main(){
	freopen("input.txt", "rt", stdin);
	scanf("%d", &n);
	DFS(1);
	return 0;
}

 

코드를 풀어서 그림으로 설명하면 아래와 같다.

(코드에 있는 DFS함수를 줄여서 D로 칭하겠다.)

부모노드로부터 왼쪽가지로 가면 해당되는 인덱스의 ch배열에 1을 넣는다.

부모노드로부터 오른쪽가지로 가면 해당되는 인덱스의 ch배열에 0을 넣는다. 

 

위와 같은 과정을 반복하는 것이 핵심이다.

 

D(1)의

왼쪽가지에는 ch[1]=1가 들어가며 오른쪽가지에는 ch[1]=0가 들어간다.

마찬가지로 D(2)의

왼쪽가지에는 ch[1]=1가 들어가며 오른쪽가지에는 ch[1]=0가 들어간다.

이런식으로 D(3), D(4)도 진행되며

D(4)함수가 호출되면 if(L==n+1)이 treu이므로 값을 print하게 된다.