백트래킹(Backtracking) / N과 M(1)

용어에 대한 정리가 필요하여 작성.

---

백트래킹이란?

- 모든 경우의 수를 전부 고려하는 알고리즘. 단 탐색 중에 유망하지 않은 경우에는 이전 단계로 돌아가서 다른 후보 탐색.

완전 탐색의 일종.

 

완전탐색(Bruteforce)과 백트래킹은 무엇이 다른가?

- 완전탐색은 모든 경우의 수를 대입. 유망성을 검사하지 않음.

 

 

간단한 백트래킹 문제 하나.

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

15649번: N과 M (1)

 

경우의 수는 nPr =  n! / (n-r)! 이 된다. 

(n = n, m = r)

 

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<unordered_map>
#include<map>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#define INF 1e9
using namespace std;
using lld = long long int;
using pii = pair<int, int>;
 
bool visited[10];
int a[10];
int n, m;
 
void solve(int dep) {
    if(dep == m) {
        
        for(int i=0; i<m; i++) {
            cout << a[i] << " ";
        }
        cout << "\n";
        return;
    }
    
    for(int i=1; i<=n; i++) {
        if(visited[i]) continue;
        
        visited[i] = true;
        a[dep] = i;
        
        solve(dep+1);
        visited[i] = false;
        
    }
    
    return;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    
    memset(visited, 0, sizeof(visited));
    
    solve(0);
    
    return 0;
}