59강

💎 문제

💎 소스코드

#include <stdio.h>
#include <vector>
#include <algorithm>
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의 완전 탐색을 이용하는 문제였다.

• DFS의 완전탐색 이라고 하는 것은 모든 경우의 수를 탐색하면서 정답을 찾는 방법이다.

• 그래서 이 문제의 경우에는 부분집합을 구하는 것이기 때문에, 각 원소에 대하여 해당 원소가 있을수도 또는 없을 수도 있다. 이를 이용해서 트리를 만들면 된다.

• 트리는 각 레벨 단계는 같은 원소를 나타내도록 한다. 하지만, 해당 원소가 만약의 부모 노드의 왼쪽 위치의 자식이라면 부모노드가 부분집합에 포함되도록, 그리고 오른쪽에 있다면 포함되지 않도록 하여 값을 배열에 값을 저장합니다.

• 이렇게 저장된 값들은 입력받은 n의 값보다 커졌을 때 출력하게끔 해줍니다.

• 이 코드를 보면 꽤나 아름답다. 재귀 호출을 통해서 왼쪽과 오른쪽 각각이 1인지 0인지를 모두 확인 할 수 있기 때문이다. 이렇게 하는 방법은 전위순회에서 모두가 1일때에 대해서 확인을 하고 중위순회 단계에서 배열에 있는 값을 0으로 하나씩 바꾸면서 트리를 올라간다. 그렇게 다 올라가서 헤드에 맞부딪혀서 헤드 부분이 0으로 되면, 중위 순회 단계가 끝나고 트리의 오른쪽을 확인하게 된다. 여기서 후위순회 단계에서 배열의 값을 넣어주지 않았기 때문에 1을 포함하지 않는 부분집합 즉 2로 시작하는 부분집합을 찾는다.

• 이 문제를 통해서 확실히 DFS 개념을 이용한 재귀호출에 관한 내용을 정리 할 수 있었던 것 같다. 여기서 가장 중요한 점은 현재 이 DFS는 진짜 트리를 그리는 것은 아니였다는 것이다. 함수를 트리의 순회순서대로 출력하는 것이라고 생각하면 편할 것 같다. 즉 깊이우선탐색을 하지만 이는 노드를 탐색한 것이 아니라, 함수를 호출하는 순서를 탐색한 것이라고 생각을 해야 할 것 같다.