백트래킹

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘. 즉, 현재 상태에서 가능한 모든 선택지를 다 플레이해보는 방법. 

 

백트래킹은 상당한 구현력을 필요로 하고 실수하기도 쉽다. 또한 재귀의 특성상 틀리더라도 실수한 부분을 찾기가 정말 힘들어서 많은 시간을 할애해 개념을 익히고 연습을 해야하고, 그렇지 않으면 풀이는 대충 알겠는데 그 풀이를 코드로 옮겨내지 못해서 문제를 틀릴 확률이 크다. 

그래도 한편으로는 그렇게 응용을 할 수 있는 건덕지가 많지는 않기 때문에 예제들을 꼼꼼하게 풀고 BFS를 배울 때와 비슷하게 기본적인 코드의 형태를 익혀두면 할만할것이다. 

 

백준 15649번-N과 M

비어있는 리스트에서 시작해 수를 하나씩 추가하면서 길이가 M인 수열이 완성되면 출력하는 방식으로 구현할 수 있다. 

 

#include <bits/stdc++.h>
using namespace std;

int n,m;
int arr[10];
bool isused[10];	//특정 수 쓰였는지 T/F

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);
}

- next_permutation 함수 

STL에 algorithm 헤더파일을 추가하면 next_permutation을 사용하여 순열을 구할 수 있다. 

next_permutation : 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true를 반환한다. 다음 순열이 없다면 false를 반환.

// next_permutation을 통해서 다음 순열 구하기
	do{

		for(int i=0; i<4; i++){
			cout << v[i] << " ";
		}

		cout << '\n';

	}while(next_permutation(v.begin(),v.end()));

next_permutation으로 조합 만들기. 

int a[4]={0,0,1,1};
do{
	for(int i=0;i<4;i++){
    	if(a[i]==1)
        	cout<<i+1;
    }
    cout<<'\n';
}while(next_permutation(a,a+4);