[BaekJoon/백준] 10974번 - 모든 순열

 

dfs의 아이디어를 이용해 풀 수 있었다.

#include <iostream>
#include <vector>

using namespace std;

int N;

bool check[9]; // 1 ~ 8 사용
vector<int> v;



void dfs(int count) {
    
    
    if(count == N) {
        
        for(int i = 0; i < N; i++) {
            cout << v[i] << " ";
        }
        cout << "\n";
        
        
    }
    
    for(int i = 1; i <= N; i++) {
        
        if(!check[i]) {
            
            check[i] = true;
            v.push_back(i);
            
            dfs(count + 1);
            
            check[i] = false;
            v.pop_back();
            
        }
        
    }
    
    
}


int main() {
    
    
    cin >> N;
    
    dfs(0);
    
    
}

check 배열을 두어서 체크해나가면서 vector에 값을 추가하고

dfs 내부의 for문은 무조건 1부터 시작하여, 뒤를 돌아볼 수 있는 특징이 있다.