정의

• 현재 상태에서 가능한 모든 후보군을 따라 들어가면서 탐색하는 알고리즘
• 게임에서 선택지가 갈릴 때, 문제 생기면 다시 세이브 & 로드 해서 다른 선택지를 골라본다.
• 그래프의 DFS의 개념을 포함하는 듯 하다. (개인적인 의견)

백트래킹의 흐름도

유명한 문제 BOJ N과 M (1)

• 네이버 웹툰 1번 문제 이걸로 풀 수 있었을 지도??

  • 백 트래킹의 구현

  #include <bits/stdc++.h>
  using namespace std;
  
  int n, m;
  int arr[10]; //선택한 숫자를 담을 배열
  bool isused[10]; // 탐색했는지 확인할 배열
  
  void func(int k) {
  	if(k == m) { //base condition
  		for(int i = 0 ; i<m; i++) {
  			cout << arr[i] << ' ';
  		cout << '\\n';
  		return;
  	}
  
  	for(int i = 1; i<=n; i++) {
  		if(!isused[i]) { // arr[i]를 순서대로 채우다가 채워지지 않은 부분이 발견되었을 때,
  			arr[k] = i; // i의 값, 처음에 n으로 입력한 limit값에 기반하여 For문으로 넣음
  			isused[i] = 1; // 사용했다는 표시를 해줌
  			func(k+1); // 계속 파고 들어가면서 모두 탐색하고 함수 빠져 나오면 
  			isused[i] = 0; //이슈의 [i]를 false 해줌, 새로 넣기 위해
  			//k+1 .. k+1.. 들어갈 때마다 isused를 true하고 false하고를 반복할 거임.
  		}
  	}
  }
  
  int main(void) {
  	ios::sync_with_stdio(0);
  	cin.tie(0);
  	cin >> n >> m;
  	func(0);
  }