[PS / C++] 백준 #15663 N과 M (9)

문제 링크 & 태그

https://www.acmicpc.net/problem/15663
백트랙킹

풀이

permutation 문제인데, 같은 수가 여러 번 입력될 수 있고, 중복되는 순열은 출력하면 안된다.

cnt와 v라는 두 개의 벡터를 만들고, cnt에는 입력으로 들어오는 수의 개수를 저장하고, v 벡터에는 중복되지 않게 들어오는 수를 하나씩만 넣었다.
순열의 출력 결과가 사전 순으로 출력되어야 하기에, v를 정렬해주었다.

백트랙킹을 하는 함수인 dfs를 작성했는데, 벡터 v를 차례대로 돌며 만약 cnt가 남아있다면, 그 수를 ans 벡터에 푸시하고 cnt를 하나감소시킨 후 dfs를 다시 호출하였다. 그러면 다시 호출된 dfs에서는 다시 v 벡터의 처음 값(가장 작은 값)부터 돌며 cnt가 남아있는 수를 ans에 푸시하고 dfs를 호출하여 ans의 크기가 M이 될 때까지 반복한다.
재귀 호출 뒤에는 cnt값을 다시 증가시키고, ans에 방금 넣었던 값을 뺀뒤, 반복문을 계속 진행해서 v[i]는 선택하지 않고, v[i+1]을 처리하는 과정으로 넘어간다. 이때는 dfs를 다시 호출하지 않고, 반복문으로 넘어가야하는데, 여기서 dfs를 다시 호출하면 그 dfs에서 방금 했던 과정을 반복하게 되므로 재귀함수가 무한으로 호출된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
vector<int> v;
vector<int> ans;
vector<int> cnt(100001, 0);
typedef long long ll;

int N, M;

void dfs(vector<int>& ans, vector<int>& cnt) {
    if(ans.size() == M) {
        for(int i=0; i<M; ++i) cout << ans[i] << ' ';
        cout << '\n';

        return;
    }

    for(int i=0; i<v.size(); ++i) {
        if(cnt[v[i]] == 0) continue;
        
        ans.push_back(v[i]);
        cnt[v[i]]--;
        dfs(ans, cnt);
        ans.pop_back();
        cnt[v[i]]++;
        // dfs(ans, cnt);
    }
}

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

    cin >> N >> M;

    for(int i=0; i<N; ++i) {
        int a;cin >> a;
        cnt[a]++;
        if(cnt[a] == 1) v.push_back(a);
    }

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

    dfs(ans, cnt);

}