[BOJ] C++ 15655 N과 M (6) - 제한이 까다로운 백트래킹

15655번: N과 M (6)

예제 1                                                                                                                                                                                       

3 1
4 5 2

ans :
2
4
5

예제 2                                                                                                                                                                                       

4 2
9 8 7 1

ans : 
1 7
1 8
1 9
7 8
7 9
8 9

---

수열을 사전순으로 출력하되 중복을 제거해야 한다. 참고로 1 7과 7 1은 같은 수열로 본다. 일반적인 백트래킹에서 중복을 제거해 주면 풀릴 것 같다.

 

백트래킹에 대한 설명 없이 바로 풀이를 할 예정입니다. 기본 백트래킹 코드를 잘 모르거나 백트래킹이 익숙하지 않으면 아래 게시글을 꼭 읽어보길 바랍니다!!

[알고리즘] 백트래킹 - 재귀를 통한 구현과 응용 문제

---

직접 트리를 만들어 보면서 풀면 M에 상관없이 k=0 일때만 모든 숫자를 방문하고 그 외에는 1 4 7 수열을 예로 들면 4_까지 트리를 채운 경우 4 다음 숫자부터 방문하면 중복 없이 트리를 만들 수 있다. 4 다음 숫자가 뭔지 index를 알아야 하는데, 답을 저장할 배열 res를 pair <int, int> 형으로 선언해서 res[k]. second를 k번째로 채운 숫자의 index로 설정해서 해결했다.

사전순으로 출력해야 하므로 당연히 배열을 정렬해줘야 한다.

/** BackTracking 15655 N과 M (6) **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int arr[10];
pair<int, int> res[10];
bool visited[10];
int n, m;

void func(int k)
{
    if (k == m)
    {
        for (int i = 0; i < m; i++)
            cout << res[i].first << ' ';
        cout << '\n';
        return;
    }
    int starting_idx = 0;
    if (k >= 1)
        starting_idx = res[k - 1].second;
    for (int i = starting_idx; i < n; i++)
    {
        if (!visited[i])
        {
            res[k] = make_pair(arr[i], i);
            visited[i] = true;
            func(k + 1);
            visited[i] = false;
        }
    }
}

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

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    sort(arr, arr + n);

    func(0);
}