백트래킹이란?

선택지가 있는 게임을 생각해보자. 예를 들어 1번 선택지에서 예, 2번 선택지에서 예, 3번 선택지에서 예를 눌러 A엔딩이 나왔다. 다른 엔딩을 보고싶다면 1,2번 선택지는 그대로 두고 3번 선택지에서 아니오를 누를 것이다. 그 다음 번에는 2번 선택지를 반대로 두고 진행해볼 것이다.
즉 1번 선택지에서 예를 누를 지, 아니오를 누를 지에 따라 엔딩이 나뉘고, 또 2번 선택지, 마지막 선택지에서도 엔딩이 갈리게 된다.
모든 선택지에 따라 탐색할 수 있는 엔딩이 갈린다. 이것이 백트래킹..

이런 이미지처럼 갈래를 나누어 탐색한다고 이해하면 쉬움

연습문제

백준 15649 N과 M (1)

풀이

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 구하기. 손으로 풀어보면 쉬운데 ㅠ 코드로 구현해보자.

방식은 다음과 같다.
arr 배열에서 처음 들어갈 수부터 차례로 넣고, 넣은 원소가 M개가 되면 출력.

#include <iostream>

using namespace std;

int n,m;
int arr[10];
bool isused[10];

void func(int k){ // 현재 k개까지 수를 택했음.
  if(k == m){ // m개를 모두 택했으면
    for(int i = 0; i < m; i++)
      cout << arr[i] << ' '; // arr에 기록해둔 수를 출력
    cout << '\n';
    return;
  }

  for(int i = 1; i <= n; i++){ // 1부터 n까지의 수에 대해
    if(!isused[i]){ // 아직 i가 사용되지 않았으면
      arr[k] = i; // k번째 수를 i로 정함
      isused[i] = 1; // i를 사용되었다고 표시
      func(k+1); // 다음 수를 정하러 한 단계 더 들어감
      isused[i] = 0; // k번째 수를 i로 정한 모든 경우에 대해 다 확인했으니 i를 이제 사용되지않았다고 명시함.
    }
  }
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  func(0);
}

백준 9663 N - Queen

백준 1182 부분 수열의 합