[BOJ알고리즘, C++]#15657_N과M(8), 백트래킹, 조합

 

#1. 문제

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

 

---

 

#2. 풀이

 

1. 백트래킹

https://webddevys.tistory.com/313

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

백트래킹 알고리즘은 여러 후보 경로들을 점진적으로 탐색해 나가며, 현재 경로가 해결책으로 이어지지 않는다고 판단되면 이전 레벨로 돌아가 다른 후보 경로들을 탐색하는 알고리즘입니다. 

 

2. 중복 선택 가능한 동시에 '1, 7' == '7, 1' 인 중복 없는 조합 고르기!

1. 먼저, 백트래킹 과정에서 종료 조건은 수열의 길이가 M이 되었을 때, 결과를 출력하고 종료합니다.
2. 다음으로, 현재 Index를 시작으로 재귀 호출을 수행하며 dfs() 호출 이후 수열 목록에서 현재 수를 pop_back() 해주는 게 포인트입니다.
3. 중복 선택이 가능하다는 점과 '수열'간 중복이 가능하다는 점의 차이점을 확실하게 구분해야 합니다.

 

---

 

#3. 코드

/*
    @문제 : 몇 가지 규칙들에 부합되는 N개의 자연수 중 M개의 자연수를 골라 만든 수열
    @설명
            1. 같은 수를 여러번 골라도 된다.
            2. 오름차순 정렬
            3. '조합' 형태의 백트래킹
            * 주의 : 백트래킹은 모든 조건을 만족한 시점의 레벨에서 역순으로 제거 및 새로운 조합 생성 작업이 발생한다.
*/

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

#define MAX 8

int N, M;
vector<int> v, res;

void dfs(int idx, int cnt)
{
    // #2. 거꾸로 보자, 이전 노드를 통해 조건을 만족하는지 체크하는거다.
    if(cnt == M)
    {
        for(int i=0; i<M; ++i)
            cout << res[i] << ' ';
        cout << '\n';
        return;
    }
    // #1. 현재 노드를 수열에 추가하고, 모든 수열이 완료되면 가장 마지막에 추가된 자연수를 제거하고 -1레벨로 회귀한다.
    for(int i=idx; i<N; ++i)
    {
        // 수열에 추가
        res.push_back(v[i]);
        // 재귀 
        dfs(i, cnt+1);
        // 수열 마지막 제거
        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;

        v.push_back(tmp);
    }

    sort(begin(v), end(v));

    dfs(0, 0);

    return 0;
}

 

---