[알골90제] 59번 - 부분집합 MS인터뷰 : DFS 깊이우선탐색

문제:

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요.

재귀를 이용한 완전탐색을 하며, 이진트리 전위순회 방식으로 출력하시오. 단 공집합은 출력X

 

입력

3

 

출력

1 2 3 

1 2 

1 3 

1

2 3 

2

3 

 

*풀이 : 

전위순회: 루트가 가장먼저 순회되는 것 => 왼쪽자식 => 오른쪽자식 

 

- LEVEL 1 2 3 4로 두기 => L로 컨트롤하기

- ch 배열은 0으로 초기화

- 왼쪽으로 자식함수 넘어갈때는 체크 1, 오른쪽은 체크 0하면서 호출한다.

- ch의 인덱스번호를 원소값으로 보자.

- if(L == n+1) 종료지점, 여기서 ch배열을 찍어준다. 1 2 3

- D(3)으로 다시갔다가 D(4)로 갈때 ch[L] = 0을 넣는다 L은 이때 3임

- 그다음에 다시 D(4)가 되었으니 종료하며, ch배열에 1로 찍힌부분만 찍음 1 1 

 

 

// 59번 - 부분집합 DFS 완전탐색

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>	

int n, ch[11];

void DFS(int L) {

	if(L==n+1) {
		for (int 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() {

	scanf("%d", &n);
	DFS(1); //level 1을 넘겨줌
}