[백준 15654] N과 M (5) (C++)

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

 

백트래킹

N개의 서로 다른 정수가 주어지고, 그 중에 M개를 뽑아서 만들 수 있는 가능한 수열을 사전순으로 모두 출력하는 문제

 

접근 방법

백트래킹으로 재귀함수 써서 풀었다.

재귀함수 파라미터로는 n, m, 수열을 담고 있는 배열(candidate), n개의 숫자의 방문여부를 담고 있는 배열을 갖고 다녔음

입력받은 n개의 숫자를 num array에 넣어두고(sort해줌 - 사전순으로 출력하려고), 수열의 첫째자리 부터 담아가면서 방문여부 체크하고

재귀함수 호출하기 반복

그러다가 수열이 m자리가 되면 결과 배열에 넣고 재귀함수를 종료함

 

코드를 좀..지저분하게 쓴 것 같긴한데..차차 나아지겠죠머

 

오답노트

아 근데 C++ 백준에서 돌릴 때 vector.size() 자꾸 int랑 비교하면 컴파일 에러 나서..

지금은 int 변수에 한번 담아주면 통과돼서 그렇게 하고 있는데 최대한 for(int s: vector) 이걸로 써야할 것 같음..

 

소스코드

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

vector<int> num;
vector<vector<int>> result;

void recursive(int n, int m, vector<int> arr, vector<bool> visit){
    int size = arr.size();
    if(size == m){
        result.push_back(arr);
    } else {
        for(int i = 0; i < n; i++){
            if(!visit[i]){
                vector<int> _arr = arr;
                _arr.push_back(num[i]);
                vector<bool> _visit = visit;
                _visit[i] = true;
                recursive(n, m, _arr, _visit);
            }
        }
    }
}

int main(){
    int N, M;
    cin >> N >> M;
    
    for(int i = 0; i < N; i++){
        int n;
        cin >> n;
        num.push_back(n);
    }
    
    sort(num.begin(), num.end());
    
    vector<int> arr;
    vector<bool> visit(N,false);
    recursive(N, M, arr, visit);
    
    int len = result.size();
    for(int i = 0 ; i < len; i++){
        for(int j = 0 ; j < M ; j++){
            cout << result[i][j] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}