[BOJ]15663 N과 M (9)

• sol1 : 백트래킹 재귀 DFS
  • 순열의 중복 저장 / 중복된 순열의 출력을 막는다.
  • 이를 위해 중복을 제거하는 set에 저장 후 출력

#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<int> input;
vector<int> vec(9);
vector<bool> visited(9);
set<vector<int>> ans;
//중복되는 수열 출력 불가
//사전 순으로 증가
void DFS(int depth){
    if(depth == M){
        vector<int> anstmp;
        for(int i = 0; i < M; ++i)
            anstmp.push_back(vec[i]);
        ans.insert(anstmp);
        return;
    }
    for(int i = 0; i < N; ++i){
        if(!visited[i]){
            visited[i] = true;
            vec[depth] = input[i];
            DFS(depth+1);
            visited[i] = false;
        }
    }
}
int main(){
    cin >> N >> M;
    for(int i = 0; i < N; ++i){
        int tmp;
        cin >> tmp;
        input.push_back(tmp);
    }
    sort(input.begin(), input.end());
    DFS(0);
    for(auto s : ans){
        for(auto i : s){
            cout << i << ' ';
        }
        cout << '\n';
    }
    return 0;
}

• sol2 : more efficient
  • 순열의 앞부분은 중복되지 않음
  • 뒤에 나오는 순열의 중복만 막으면 더 효울적인 코드 구성 가능

#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<int> input;
vector<int> vec(9);
vector<bool> visited(9);
//중복되는 수열 출력 불가
//사전 순으로 증가
void DFS(int depth){
    if(depth == M){
        for (int i = 0; i < M; ++i) {
          cout << vec[i] << ' ';
        }
        cout << '\n';
        return;
    }
    int tmp = 0;//직전 단계에 나온 수를 저장
    for(int i = 0; i < N; ++i){
    	//이전 수열의 마지막항 = 새로운 수열의 마지막항이면 중복수열(제외)
        if(!visited[i] && tmp != input[i]){
            visited[i] = true;
            vec[depth] = input[i];
            tmp = vec[depth];
            DFS(depth+1);
            visited[i] = false;
        }
    }
}
int main(){
    cin >> N >> M;
    for(int i = 0; i < N; ++i){
        int tmp;
        cin >> tmp;
        input.push_back(tmp);
    }
    sort(input.begin(), input.end());
    DFS(0);
    return 0;
}