백준 BOJ 15649 - N과 M(1)

간단한 dfs문제

1번부터 순회하면서 출력해주면

반드시 사전순을 충족하게 짤 수 있다.

www.acmicpc.net/problem/15649

15649번: N과 M (1)

arr[]은 출력할 답을 저장하는 배열이고,

visit[]은 방문여부를 저장해준다. ( 같은 수가 중복으로 나오는것을 방지하기 위해서 )

 

#include <stdio.h>
#include <vector>

using namespace std;

int n,m;
int arr[10] = {0};
int visit[10] = {0};

void dfs(int k){
	if(k==m){
		for(int i=0; i<m; i++) printf("%d ", arr[i]);
		puts("");
		return;
	}
	for(int i=1; i<=n; i++){
		if(!visit[i]){
			visit[i] = 1;
			arr[k] = i;
			dfs(k+1);
			visit[i] = 0;
		}
	}
}

int main(){
	scanf("%d %d", &n, &m);
	dfs(0);
	return 0;
}

깔끔하게 AC.