[10974] 모든 순열(C++)

문제

바로가기

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다. 

 

 

출력

첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

 

 

해결 방법

 

 

내 코드

// [10974] 모든 순열
// 브루트포스, 백트래킹
#include <iostream>
using namespace std;

bool visited[8];
int n, arr[8], tmpArr[8];

void dfs(int idx, int depth)
{
    if(depth == n) {
        for(int i = 0; i < n; i++) {
            cout << tmpArr[i] << " ";
        }
        cout << '\n';
        return;
    }
    for(int i = 0; i < n; i++) {
        if(visited[i] == false && i != idx) {
            visited[i] = true;
            tmpArr[depth] = arr[i];
            dfs(i, depth + 1);
            visited[i] = false;
        }
    }
}

int main(void)
{
    cin >> n;
    for(int i = 0; i < n; i++) {
        arr[i] = i+1;
    }
    dfs(-1, 0);
}