백준 10974번 모든 순열 - C++ 풀이

---

 

1. DFS를 사용하여 모든 순열을 구한다.
2. DFS 과정에서 각 숫자의 사용 여부는 비트 마스크로 나타낼 수 있다.

 

1. DFS를 사용하여 모든 순열을 구한다.

 DFS를 돌면서, 매 depth마다 선택한 적 없는 숫자 중 하나의 숫자를 선택하면 모든 순열을 구할 수 있다.

 

2. DFS 과정에서 각 숫자의 사용 여부는 비트 마스크로 나타낼 수 있다.

 이때 각 숫자를 이전 depth에서 선택했었는지 여부를 비트 마스크로 나타내어 준다.

 

반응형

---

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> permu;

void DFS(int depth, int mask) {
    if (depth == N) {
        for (auto x : permu) cout << x << " ";
        cout << "\n";
        return;
    }
    
    for (int i=1; i<=N; i++) {
        if ((mask & (1 << i)) != 0) continue;
        
        permu.push_back(i);
        DFS(depth+1, mask|(1<<i));
        permu.pop_back();
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    
    DFS(0, 0);

    return 0;
}