[Algorithm] 순열

- 순열은 조합과 다르게 뽑힌 아이들에도 순서가 있다..!!

 과거에 뽑은 아이들도 다시 확인을 해주어야 한다...!!!!

 조합은 { 1, 2, 3 }, { 2, 1, 3 }이 같은 취급을 받는다.

 순열은 { 1, 2, 3 }, { 2, 1, 3 }이 다른 취급을 받는다.

 

#include <iostream>
#include <vector>
#define MAX 5

using namespace std;

int arr[MAX];
int check[MAX];
vector<int> v;
void print(){
    for (int i = 0; i < v.size(); ++i) {
        cout << v[i] << ' ';
    }
    cout << '\n';
}

void DFS(int cnt){
    if(cnt == 3) {
        print();
        return;
    }
    for (int i = 0; i < MAX; ++i) {
        if(check[i]) continue;
        check[i] = true;
        v.push_back(arr[i]);
        DFS(cnt + 1);
        check[i] = false;
        v.pop_back();
    }
}
int main(){
    ios::sync_with_stdio(false);
    cout.tie(NULL);

    for (int i = 0; i < MAX; ++i) {
        arr[i] = i + 1;
    }
    DFS(0);
    return 0;
}

 조합과는 다르게 DFS를 부를때 전달하는 파라미터가 cnt 하나로 줄었다. 조합 때에 만약 1을 뽑은적이 있다면 그 이후에는 다시는 1을 뽑을 필요가 없게 하기위해 시작점을 같이 파라미터로 넘겨줬다. ( { 1, 2, 3 } 을 뽑은 후에 { 2, 1, 3 } 이런식으로 뽑지 않기 위해)

 

 순열에서는 { 1, 2, 3 }, { 2, 1, 3 } 이 다른 취급을 받으므로 시작점을 기록할 필요가 없다. 또한 순서가 있으므로 vector에 인자들을 기록했다. 또 DFS를 부른 후에는 vector의 인자를 pop() 한다.

 

 직접 코딩을 해보며 기록해보는 것이 가장 좋은 공부방법이라고 생각한다~!

 

참조 ref) https://yabmoons.tistory.com/100?category=838490