(15649) N과 M (1)

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

단계별로 풀어보기

20단계(백트래킹) 1번째

 

 

 

백트래킹이란 브루트 포스처럼 모든 경우를 탐색하지만 유망하지 않은 가능성은 가지치기하여 경우의 수를 줄이는 방식이다. 주로 DFS 방식으로 구현한다.

아무튼 지난 단계에서 했던 재귀를 이용해 구현하면 된다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n >> m;
  
  vector<int> v(m);
  vector<bool> check(n+1, false);
  
  auto func= [&](auto self, int depth) -> void {
    if(depth==m){
      for(int elem:v)  cout << elem << " ";
      cout << "\n";
      return;
    }
    
    for(int i=1;i<=n;i++){
      if(check[i])  continue;
      
      v[depth]= i;
      check[i]= true;
      self(self, depth+1);
      check[i]= false;
    }
  };
  
  func(func, 0);
  
  return 0;
}