백준 15654번, N과 M(5)

백준 15654번 c++ 문제풀이

문제:

백준 15654

풀이:

1. 깊이우선탐색으로 진행
2. 재귀함수 dfs를 통해 중복되지 않게 수열을 만들어준다. 수열 중 몇번째(count)인지 다음 수열을 선택할 때 넘겨준다.
3. 선택된 수는 arr[count]에 저장해준다.
4. count가 m이랑 같다면 그 수열을 출력해준다.
5. 다음 수열 값을 정해줄 때는 중복가능하지 않기에, int visited를 통해 몇번째 인덱스를 방문했는지 표시해준다.

코드:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int arr[9] = {0,};
int visited[9] = {0,};

void dfs(vector<int> v, int count, int n, int m){

    if(count==m){
        for(int i=0;i < m;i++){
            cout << arr[i] << " ";
        }
        cout << "\n";
    }else{
        for(int i=0;i<n;i++){  
            if(visited[i] == 0){
                arr[count] = v[i]; 
                visited[i] = 1;
                dfs(v, count+1, n, m);//수열 중에 다음값을 선택한다.
                visited[i] = 0;  //새로 다음 수열을 만들려면 방문 정보를 초기화 해줘야 함
            }
        }
    }
} 

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

    int n, m;

    cin >> n >> m; //n까지의 자연수중, m개를 골라 만드는 수열

    vector<int> v;

    for(int i=0;i<n;i++){
        int input;

        cin >> input;

        v.push_back(input);
    }

    sort(v.begin(), v.end()); //내림차순 정렬

    dfs(v, 0, n, m);
    return 0;
}

감사합니다.