N과 M(1) C++ - 백준 15649

https://www.acmicpc.net/problem/15649

이 문제는 백트래킹 문제이다.

dfs로 모든 경우를 탐색할 때 visited 배열을 사용해서 중복을 체크한다.
(visited 배열로 중복 확인이 가능한 이유는 dfs를 호출하게 되면 호출한 경우에서만의 visited 배열을 사용하기에 가능하다.)

코드는 다음과 같다.

#include <bits/stdc++.h>
#define FASTIO ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define MAX 9
using namespace std;

int N;
int M;
int arr[MAX];
bool visited[MAX];

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(){
	FASTIO
	cin >> N >> M;
	dfs(0);
}