[Algorithm] 백트래킹 / c++

바킹독의 실전 알고리즘 0x0C강 정리

 

백트래킹

: 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

 

예시문제

> 주어진 수 N까지의 수를 사용해 길이가 M인 배열을 모두 구하는 문제 ( 15649번 N 과 M )

 

입력 | 4 3

1. 빈 배열로 시작

 

2. 배열[0]에 1을 넣기

 

2-1.배열[1]에 2를 넣기

2-1-1.배열[2]에 3을 넣기

2-1-2.배열[2]에 4를 넣기

 

2-2.배열[1]에 3을 넣기

2-2-1.배열[2]에 2를 넣기

2-2-2.배열[2]에 4를 넣기

 

2-3.배열[1]에 4를 넣기

2-3-1.배열[2]에 2를 넣기

2-3-2.배열[2]에 3을 넣기

 

3.배열[0]에 2를 넣기

...

 

코드

#include <iostream>
#include <algorithm>
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);
}