BOJ 1759

완전탐색이란 상태공간에서 특정한 조건을 만족하는 해를 가지는 상태를 찾기 위해 모든 상태를 만들어나가며 탐색하는 것을 말한다.
초기 상태에서 시작하여 인접한 상태들로 DFS(깊이우선탐색)을 하는 것과 같다. 완전탐색의 시간복잡도는 만들 수 있는 모든 상태의 수와 관련있으므로 최대한 상태공간을 적게 만들도록 상태를 정의하는것이 완전탐색의 포인트이다.

https://www.acmicpc.net/problem/1759 암호만들기

문제요약 :
입력으로 주어진 문자들 중 L개의 문자를 조합해 만들 수 있는 문자열 중 특정 조건을 만족하는 모든 문자열을 사전순으로 출력해야 한다.
L개의 문자로 만든 문자열은 각 문자들이 오름차순으로 배치 되어 있어야 하고, 최소 한개의 모음과 최소 두개의 자음으로 이루어져 있어야 한다.

일단 문제를 간단히 하기 위해 입력으로 주어진 문자들을 정렬한다. 그러면 여기서 완전탐색을 할때 먼저 앞에서 어떤 문자를 고른다면 남은 문자는 뒤에서만 고르면 된다. 그리고 완성된 문자열들을 모아서 따로 정렬할 필요 없이 완전탐색 과정에서 만들어지는 문자열을 사전순으로 발견된다.

함수 재귀호출 과정에서 넘기는 파라매터는 현재까지 만들어진 암호, 그리고 현재 선택가능한 가장 작은 인덱스이다. 패스워드의 길이가 L과 같아졌다면 조건의 맞는 문자라면 출력하고 함수를 종료한다.

#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int l, n;
vector<char> charVector;
char c;

void printPassword(string& password){
    int size = password.size();
    int i,cnt=0;;
    for(i=0;i<size;i++){
        if(password[i] == 'a' ||
           password[i] == 'e' ||
           password[i] == 'i' ||
           password[i] == 'o' ||
           password[i] == 'u')
            ++cnt;
    }
    if(cnt<1 || size-cnt<2) return;
    printf("%s\n",password.c_str());
}

void make(string& password, int smallest){
    if(password.size()==l){printPassword(password);return;}

    for(int next = smallest;next<n;next++){
        password.push_back(charVector[next]);
        make(password,next+1);
        password.pop_back();
    }
}

int main(){
    scanf("%d%d",&l,&n);
    for(int i=0;i<n;i++){
       scanf(" %c",&c);
       charVector.push_back(c);
    }
    sort(charVector.begin(),charVector.end());
    string password;
    make(password,0);
    return 0;
}