백 트래킹 공부 BOJ 15649

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

요구사항 : 1~n까지의 숫자중에 m개의 숫자를 쓰는 수열을 모두 출력

예시 : n = 3; m=2의 경우

출력

1 2
1 3
2 1
2 3
3 1
3 2

규칙성
m-1 개의 숫자를 사용 후 마지막 자리를 변경 n개의 숫자를 모두 사용하면
m-2 개의 숫자를 변경 후 다시 위 방법을 사용

코드

#include <bits/stdc++.h>

using namespace std;

int n,m;
int arr[10];
bool isused[10]; //특정수가 쓰였는지 확인을 위한 배열

void func(int k){
    if(k==m){
        for(int i=0; i<m; i++)
            cout<<arr[i]<<" ";
        cout<<'\n';
        return ;
    }
    for(int i=1; i<=n; i++){
        if(!isused[i]){
            arr[k] =i;
            isused[i]=1;
            func(k+1);
            isused[i] = 0;
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    func(0);

}

모든 루트를 들르는게 DFS와 동일한 구조 같다 생각하여 검색을 해본 결과
DFS의 경우 중간에 틀린 경로를 발견해도 그대로 진생되는 반면 백트래킹의 경우 중간에 틀린것을 발견하면 이전 노드로 돌아가서 불필요한 탐색을 줄인다는 점을 알았다!

참고한 블로그 : https://blog.encrypted.gg/945