백준 15649 c++

안녕하세요 오늘은 dfs을 이용하여 n개중에 순서 상관있이 m개의 숫자를 뽑는 모든 경우의 수를 출력하는 문제를 풀겠습니다.

 

전략:

1. dfs라는 return 값이 없는 함수를 만들어주고 cnt를 매개변수로 받아줍니다.

2. 1부터 N까지 반복하는 반복문을 만듭니다. 그 뒤, visited[i]가 false이면 i를 방문한 적이 없는 것이므로, visited[i]를 방문상태, 즉 true로 바꾸고 arr[cnt] = i를 해줌으로 cnt번째로 출력할 값을 i로 설정합니다.

3. 그리고 dfs(cnt+1)을 해줍니다. 그 과정이 끝나면 다시 전 노드로 와야하므로 visited[i]를 false로 만듭니다.

코드:

#include <bits/stdc++.h>
using namespace std;
int arr[9] = {0, };
bool visited[9] = {0, };
int N, M;
void dfs(int cnt){
	if(cnt == M){
		for(int i= 0; i<M; ++i){
			cout<<arr[i]<<" ";
		}
		cout<<"\n";
		return;
	}
	for(int i = 1; i<=N; ++i){
		if(!visited[i]){
			visited[i] = true;
			arr[cnt] = i;
			dfs(cnt+1);
			visited[i] = false;
		}
	}
	
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>N>>M;
	dfs(0);
}