[C++][백준] 15649 N과 M(1)

이번 문제는 재귀함수를 사용한 백트래킹 문제이다.

백트래킹이 뭘까?

모든 경우의 수를 전부 고려하는 알고리즘으로 특정 해를 찾다가 해의 조건이 아니게 되면 다시 돌아가는 과정을 반복해 모든 해를 찾는 방법이다. 트리와 같은 구조에서 유용하다.

 

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

 

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

 

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며,
각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

머릿속으로 생각하기에는 이런 방법이 있을 것이다.

또한 이런 식으로 앞에 같은 것이 나왔다면 다시 돌아가는 방법도 있다.

그렇다면 이 방법을 구현하려면 어떻게 해야 할까?

아래 코드를 보자.

#include <bits/stdc++.h>

using namespace std;
int N,M;
int used[9];// 사용여부 판단
int num_set[8]; // 만들어진 숫자셋

void Permu(int choosed){
    if(choosed == M) // 종료조건
    {
        for(int i=0; i<M; i++){
            cout<< num_set[i] << ' ';
        }
        cout << '\n';
        return;
    }
    for(int j=1; j<=N; j++){
        if(!used[j]){
            num_set[choosed] = j;
            used[j] = 1;
            Permu(choosed+1);
            num_set[choosed] = 0;
            used[j] = 0;
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    Permu(0);
    return 0;
}

먼저 (1 ≤ M ≤ N ≤ 8) 이기 때문에 숫자셋을 저장할 8칸짜리 num_set 배열을 선언해주고, 사용되었음을 확인하기 위한

9칸짜리 used 배열을 선언해주었다.

used배열이 9칸인 이유는 각 칸의 index로 사용 여부를 알아보기 위함이다.

다음은 Permu 함수를 작성하였다. 인자는 choosed라는 int값을 넣어주었는데, 이것은 현재 숫자 배열의 크기를 알려주는 값이다.

Permu함수는 재귀함수이기 때문에 종료 조건이 있어야 한다. 

종료 조건은, choosed의 값이 M과 같을 때로, num_set배열에 있는 모든 값을 반환한다.

종료 조건이 아닐 때의 작동은, 1부터 N까지 반복문을 돌리면서 사용한 숫자와 그렇지 않은 숫자를 판별한다.

만약 해당 숫자가 사용되지 않았다면, num_set 배열에 넣고 used배열에 사용했음을 의미하는 1을 넣어준다.

그 다음 Permu함수의 인자값을 1 증가시켜준 다음 호출해준다. 호출이 끝나면 다시 해당 index의 배열을 비우고 used값도 비워준다.