#include <stdio.h>
int n;
int a[11];
void DFS(int x)
{
if(x == n+1)
{
for(int i = 1; i <= n; i++)
if(a[i] == 1)
printf("%d ", i);
puts("");
}
else
{
a[x] = 1;
DFS(x+1);
a[x] = 0;
DFS(x+1);
}
}
int main()
{
scanf("%d", &n);
DFS(1);
return 0;
}
1. 위 그림은 n = 3 일 때 이진트리 깊이우선탐색을 표현한 트리 구성표이다.
DFS(int x) 에서 x는 트리의 레벨을 의미한다. 맨 위가 1레벨, 한 번 분기 될 때마다 레벨이 1씩 증가한다.
빨간원이 2레벨, 주황원이 3레벨, 노란원이 4레벨이 된다.
부모노드 기준으로 왼쪽 자식노드는 a[x] = 1을, 오른쪽 자식노드는 a[x] = 0을 수행한다.
최종 노드에 도달하게 되면, 배열 a 의 원소를 확인하여 해당 인덱스의 원소가 1이라면 그 인덱스를 출력한다.
puts() 함수는 입력받은 문자열을 '\0'(입력의 끝)이 될 때까지 출력하고 개행(\n)까지 출력해준다.
puts("")는 개행만을 출력한다.
최종 트리의 모습은 다음과 같다. x == 4가 되는 순간 x = 3 일 때 최종노드라고 판단하고 더이상 진행하지 않는다. 진행하지 않고 배열 a의 원소를 확인하면서 1이라면 그 인덱스를 출력한다.
맨 왼쪽 노드는 a = [1,1,1] 이므로 1 2 3을 출력하고 puts("")에 의해 줄바꿈을 한다.
그 다음 노드는 a = [1,1,0] 이므로 1 2 를 출력하고 줄바꿈을 한다.
다음은 (1, 3), 1, (2, 3), 2, 3 을 출력한다.
