[BOJ알고리즘, C++]#15654_N과M(5), 백트래킹, 순열 백트래킹

 

#1. 문제

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

 

---

 

#2. 풀이

 

1. 백트래킹

[알고리즘]#6_백 트래킹

백트래킹 알고리즘은 문제 해결을 위해 여러 후보책들을 점진적으로 탐색하는 알고리즘입니다. 백트래킹 알고리즘은 현재 경로가 해결책으로 이어질 수 없다고 판단되면 이전 단계로 돌아가 다른 후보 경로에 대한 탐색을 진행합니다. 일반적으로, 백트래킹 알고리즘은 재귀 호출을 활용한 DFS를 통해 구현합니다.

 

2. 순열 백트래킹 유형, 순서가 중요하며 '중복 선택'이 불가능하다.

1. 순열 백트래킹 유형의 문제입니다. 주어진 자연수 목록에서 각 원소를 한 번씩만 선택할 수 있고, 그 순서에 따라서 같은 자연수 조합이라도 다른 부분 수열로 취급됩니다.
2. 백트래킹 구현 과정에서 같은 자연수가 두 번 이상 선택되는 것을 방지하기 위해, 각 원소에 대하여 방문 여부를 체크해 주는 조합 백트래킹을 설계해야 합니다.

 

---

 

#3. 코드

 

/*
    @문제 : 자연수 N개를 통해 길이가 M개인 수열을 만드는 경우의 수, 사전 순으로 출력
    @설명
            1. 주어진 입력에 대하여 정렬을 한 번 수행
            2. 순열(nPr) 백트래킹
            3. 결과 출력
*/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX 8

int N, M;
vector<int> arr;
vector<int> res;
vector<bool> visited(MAX, false);

void dfs(int depth)
{
    if(depth == M)
    {
        for(int i=0; i<M; ++i)
            cout << res[i] << ' ';
        cout << '\n';
        return;   
     }

     for(int i=0; i<N; ++i)
     {
        if(!visited[i])
        {
            visited[i] = true;
            res.push_back(arr[i]);
            dfs(depth+1);
            visited[i] = false;
            res.pop_back();
        }
     }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    for(int i=0; i<N; ++i)
    {
        int tmp;
        cin >> tmp;

        arr.push_back(tmp);
    }

    sort(begin(arr), end(arr));

    dfs(0);

    return 0;
}

 

---