[알고리즘 문제] 백준10974 - 모든 순열

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

10974번: 모든 순열

 

c++에서 순열을 구하는 api가 제공되기는 한데 한번 직접 코드로 짜보고 싶었다.

생각보다 쉽게 된 것 같다. dfs로 풀었고, 각 숫자가 중복되어 들어가면 안되기 때문에 각 숫자를 사용할 때 마다 체크를 해주었다.

#include <iostream>
#include <vector>

using namespace std;
int n;
int check[9] = {0};

void dfs(vector<int> &v)
{

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

int main()
{
    cin >> n;
    vector<int> v;
    dfs(v);
    return 0;
}