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

1759번: 암호 만들기

 

백트래킹 연습하기 #1

Stack Permutation C++

이전에 스택을 이용해 permutation을 구현한 코드처럼 C개의 문자중에서 L개를 뽑는 경우를 모두 출력하는 문제이다

 

추가된 조건들

1. 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되어있을 것

2. 암호를 이루는 알파벳은 모음을 최소 1개 가져야 하고, 자음을 최소 2개 가져야 한다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int L, C;
vector<char> str;
char ret[16];
bool visit[16] = {false, };
 
// 현재 문자가 모음이면 true
bool is_vowel(char c){
    if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u') return true;
    else return false;
}
 
void dfs(int pos, int d, int vow, int con){
    if(d == L){
        if(vow == 0 || con < 2) return;
        for(int i = 0; i < L; i++){
            cout << ret[i];
        }
        cout << "\n";
        return;
    }
    
    //str[0] 부터 str[C-1]까지 탐색
    for(int i = pos; i < C ; i++){
        if(visit[i]) continue; //방문했을경우 다음 글자로 넘어감
        
        ret[d] = str[i]; // 결과가 될 현재 깊이 위치에 str의 문자를 입력
        if(is_vowel(ret[d])) vow++; //모음과 자음의 갯수를 카운팅
        else con++;
        
        visit[i] = 1;
        dfs(i+1, d+1, vow, con);
        visit[i] = 0;
        if(is_vowel(ret[d])) vow--; // 다시 빼주기
        else con --;
        
    }
}
 
int main(){
    cin >> L >> C;
    char c;
    for(int i = 0; i < C; i++){
        cin >> c;
        str.push_back(c);
    }
    sort(str.begin(), str.end());
    
    dfs(0, 0, 0, 0);
    
    return 0;
}