10974_모든순열

10974_모든순열

기본적인 n을 입력하고 n까지의 모든 순열을 구하는 문제이다. 대부분 next_permutation으로 풀었지만 dfs로 풀어봤다. 코드는 다음 그림을 그리게 된다.

• visited[1] = 1

• dfs(1)

  • visited[2] = 1

  • dfs(2)

    • visited[3] = 1

    • dfs(3)

    • visited[3] = 0

  • visited[2] = 0

• visited[1] = 0

한번 방문한 곳은 1로 저장하고, 다음 번 방문시 방문한 곳은 다시 가지 않는다.

code

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
​
int num;
int visited[10];
int arr[10];
​
void dfs(int number, int index){
    arr[index] = number;
    if(index == num){
        for(int i=1;i<=num;i++){
            cout << arr[i] << " ";
        }
        cout << endl;
        return;
    }
    
    for(int i=1;i<=num;i++){
        if(visited[i]) continue;
        visited[i] = 1;
        dfs(i, index+1);
        visited[i] = 0;
    }
    
}
​
int main() {
    
    cin >> num;
    for(int i=1;i<=num;i++){
        visited[i] = 1;
        dfs(i,1);
        visited[i] = 0;
    }
    
}