Stack Permutation C++

순열을 구하기위해 dfs를 사용했는데 visit 배열 대신 stack을 사용해서 구현해보았음

 

n이 8이 넘어가면 하루종일 걸려요.. 모든 경우의 수를 출력해주기 때문에 어쩔 수 없다

 

if(node == N) 부분의 for 문을 보면 N이 i에 대한 조건으로 있는데 이 N을 입력받은 N보다 작게 바꿔주면

ex ) N이 6일 때 4로 설정

-> 6까지의 숫자 중 4개를 골라 만들 수 있는 모든 순열이 출력된다

 

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> _stack;
int N, check[10] = {0, };
 
void dfs_stack(int node){
    if(node == N){
        for(int i = 0; i < N; i++){
            cout << _stack[i] << " ";
        }
        cout << endl;
        return;
    }
    for(int i = 0; i < N; i++){
        if(check[i] == 0){
            _stack.push_back(i+1);
            check[i] = 1;
            dfs_stack(node+1);
            _stack.pop_back();
            check[i] = 0;
        }
    }
}
 
int main(){
    cin >> N;
    dfs_stack(0);
    return 0;
}