[백트랙킹]백준1759번 암호만들기

백준1759

백트랙킹을 연습할 수 있는 문제이다.

알파벳들이 주어졌을 때, 조건에 따라 가능한 모든 조합을 테스트 해보면 된다.

a부터 시작해 백트랙킹을 통해 한자리 한자리 채워가며 가능한 조합을 모두 확인하고 그 다음으로 큰 문자로 넘어가서 다시 가능한 조합을 모두 확인하면 된다.

백트랙킹의 base condition은 depth (백트랙킹 함수로 들어오는 매개변수)가 암호의 길이와 같아졌을 경우이다.

최소 한 개의 모음과 두 개의 자음으로 이루어졌다는 사실을 꼭 조건에 넣어줘야 한다.

모음과 자음을 따로 count 하여 base condition에 도달할 경우 조건을 확인하도록 하였다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<char> alphabet;
char arr[15];
bool isused[15];
int L, C;
int cnt = 0;
int cnt2 = 0;
void btk(int n){
    if(n==L && cnt > 0 && cnt2 >=2){
        for(int i=0;i<L;i++){
            cout << arr[i];
        }
        cout << endl;
        return;
    }
    for(int i=0;i<C;i++){
        if(!isused[i]){
            if(n>0){
                if(arr[n-1] < alphabet[i]){
                    if(alphabet[i]=='a' || alphabet[i]=='e' || alphabet[i]=='i'||alphabet[i]=='o'||alphabet[i]=='u'){
                        cnt++;
                    }
                    else{
                        cnt2++;
                    }
                    arr[n] = alphabet[i];
                    isused[i] = true;
                    btk(n+1);
                    isused[i] = false;
                    if(alphabet[i]=='a' || alphabet[i]=='e' || alphabet[i]=='i'||alphabet[i]=='o'||alphabet[i]=='u'){
                        cnt--;
                    }
                    else{
                        cnt2--;
                    }
                }
            }else{
                if(alphabet[i]=='a' || alphabet[i]=='e' || alphabet[i]=='i'||alphabet[i]=='o'||alphabet[i]=='u'){
                        cnt++;
                    }
                    else{
                        cnt2++;
                    }
                    arr[n] = alphabet[i];
                    isused[i] = true;
                    btk(n+1);
                    isused[i] = false; 
                    if(alphabet[i]=='a' || alphabet[i]=='e' || alphabet[i]=='i'||alphabet[i]=='o'||alphabet[i]=='u'){
                        cnt--;
                    }
                    else{
                        cnt2--;
                    }
            }
        }
    }
}

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

    cin >> L >> C;
    for(int i=0;i<C;i++){
        char temp;
        cin >> temp;
        alphabet.push_back(temp);
    }

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

    btk(0);

}