[BOJ]15649 N과 M (1) - 순열

• sol1 : 백트래킹 재귀 DFS
• 순열(Permutation) : $nPm$의 코드식 구현
  • $nPr = n! / (n - r)! = nCr * r!$
  • 앞에 나온 수 < 뒤의 나온 수
  • 이미 등록된 수 중복 불가 = visited를 통해 체크
• 고찰
  • visited가 없다면 1...1 to N...N의 수를 순환하는 수열
  • visited를 통해 방문된 수를 선점
    • 수가 오름차순으로 들어오므로, 당연히 오름차순 수열이 된다.
  • 방문이 종료되었다면, visited를 통해 선점 해제
    • 해당 수보다 작지만 앞선 수보다 큰 수가 들어갈 수 있도록

#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<int> arr(9, 0);
vector<bool> visited(9, false);
void DFS(int n){
    if(n == M){
        for(int i = 0; i < M; ++i){
            cout << arr[i] << ' ';
        }
        cout << '\n';
        return;
    }
    for(int i = 1; i <= N; ++i){
        if(!visited[i]){
            visited[i] = true;
            arr[n] = i;
            DFS(n+1);
            visited[i] = false;
        }
    }
}
int main(){
    cin >> N >> M;
    DFS(0);
}

• sol2 : NextPermutation
  • 벡터 내 순열을 쉽게 구해주는 next_permutation() 활용
    • #include <algorihtm> 헤더 필수

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
vector<int> graph;
int main(){
    cin >> N >> M;
    for(int i = 1;  i <= N; ++i)
        graph.push_back(i);
    do{
        for(int i = 0; i < M; ++i)
            cout << graph[i] << " ";
        cout << '\n';
        reverse(graph.begin() + M, graph.end());
    }while(next_permutation(graph.begin(), graph.end()));
    return 0;
}