10974. 모든 순열

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

10974번: 모든 순열

 

 

순열 알고리즘 문제이다. 브투트포스 알고리즘을 공부하면서 조합이나 순열관련된 문제들이 많이 나와서 이 둘을 다시 파헤치기 시작하게 되었다. 

 

조합은 수식으로 nCr로 표현할 수 있는데 n개의 원소 중 r개를 뽑는 모든 경우를 살피는 것을  뜻한다.

수열은 수식으로 nPr로 표현할 수 있으며, n개의 원소 중 r개를 나열하는 모든 경우의 수를 뜻한다. 

 

조합과 수열의 차이점은 for문의 시작 값이 조합은 현재 level의 값 수열은 해당 수의 시작값이다 문제에선 1로 시작했다. 

그리고 수열은 나열하는 모든 경우의 수를 체크해야하는 체크 변수가 따로 존재한다. 조합은 어떤 순서든 해당 원소들이 중복이라면 하나로 치기때문에 그렇지 않다. 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n;
bool visited[9];

void myPermu(int level, vector<int> result)
{
    if (level == n)
    {
        for (int i = 0; i < level; i++)
        {
            cout << result[i] << ' ';
        }
        cout << '\n';
        return; 
    }

    // 순열이니까 1부터 시작 체크변수로 해당 값을 가져갔다고 체크해야한다
    //조합과 다르게, 순열의 경우는 순서에 상관있게 선택해야 하므로 원소의 사용 여부를 나타내는 check 배열이 필요함.
    for (int i = 1; i <= n; i++)
    {
        if (visited[i] == true) continue; 
        visited[i] = true;  // 해당원소 사용햇으니 체크 
        result[level] = i; // 해당 인덱스 원소 선택 
        myPermu(level + 1, result); // 다음 for문으로 들어가는 역할  nPr은 r개의 포문을 중첩해서 만들어 검사하니 재귀함수로 일반화한다
        visited[i] = false; // 해당원소 사용햇으니 초기화 
    }
}

int main() {
 

    cin >> n; 

    vector<int> list;
    for (int i = 0; i < n; i++)
    {
        list.push_back(i + 1);
    }

    myPermu(0, list);
 
 

    return 0;
}