[백준] 1759 암호 만들기 c++

 

문제 링크 https://www.acmicpc.net/problem/1759

KEY

• 일반적인 백트래킹 기법에 조건을 체크하는 것이 추가된 문제이다.
• DFS로 완전탐색을 하다가 임시배열의 크기가 l이 되면 문제조건을 체크한 후, 출력한다.
• 사전 순 출력은 DFS탐색 전에 sort로 해결하였다.

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int MAX = 16;
int l,c;
vector<char> v;
vector<char> tmp;
bool check(vector<char> v) { //문제조건 체크
    int vowel = 0;
    for (int i = 0; i < v.size(); i++) {
        if (v[i] == 'a' || 
            v[i] == 'e' || 
            v[i] == 'i' || 
            v[i] == 'o' || 
            v[i] == 'u') {
            vowel++;
        }
    }
    if (vowel >= 1 && l-vowel >= 2)//모음 1개 이상, 자음 2개 이상 필수 
        return true;
    return false;
}
 
void dfs(int idx) {
    if ((int)tmp.size() == l) {
        if (check(tmp)) {
            for (int i = 0; i < tmp.size(); i++) {
                cout << tmp[i];
            }
            cout << "\n";
        }
        return;
    }
    for (int i = idx; i < c; i++) {
        tmp.push_back(v[i]);
        dfs(i + 1);
        tmp.pop_back();
    }
}
int main()
{
    cin >> l >> c;
    for (int i = 0; i < c; i++) {
        char alp;
        cin >> alp;
        v.push_back(alp);
    }
    sort(v.begin(),v.end());
    dfs(0);
 
}