[c++] 순열구하기(DFS: Depth First Search)

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int n, m, ch[100], res[100], a[100], cnt=0;;
void DFS(int L){
	int i;
	if(L==m){
		for(i=0; i<m; i++){
			printf("%d ", res[i]);
		}
		cnt++;
		puts("");
	}else {
		for(i=1; i<=n; i++){
			
			if(ch[i]==0) {
				res[L]=a[i];
				ch[i]=1;
				DFS(L+1);
				ch[i]=0;
			}
		}	
	}
}
int main() {
	freopen("input.txt", "rt", stdin);
	int k, i, j;
	scanf("%d %d", &n, &m);
	for(i=1; i<=n; i++){
		scanf("%d ", &k);
		a[i]=k;
	}
	DFS(0);
	printf("%d", cnt);
	return 0;
}

 

DFS문제로 스텍을 사용해서 구현했다.