[boj] 백준 1759 암호 만들기 - DFS

[문제]

https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

[풀이]

dfs를 이용해서 풀 수 있다. 증가하는 순서의 배열로만 암호가 만들어지므로 알파벳을 정렬 후 사용한다. depth가 암호의 길이가 되었을 때 모음과 자음의 개수를 확인해주고 조건에 일치하면 출력한다.

 

[코드]

 

// Created by strit on 2022-02-17. gold5 1759 암호 만들기 - dfs
#include <iostream>
#include <vector>
#include <algorithm>

using namespace::std;

int l, c; //암호 길이, 알파벳 개수
vector<char> v;

//a c i s t w
void dfs(string s, int idx, int depth){
    if(depth == l){
        int z = 0, m = 0; //자음, 모음
        for(int i=0; i<s.length(); i++){
            if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u' ){
                z++;
            }
            else
                m++;
        }
        if(z>=1 && m>=2){
            cout << s << endl;
        }
        return;
    }

    for(int i=idx+1; i<c; i++){
        dfs(s+v[i], i, depth+1);
    }

}

int main() {
    //가능성있는 암호를 모두 출력, 최소 한개의 자음, 두개의 모음, 증가 하는 순서로 배열
    cin >> l >> c;
    for(int i=0; i<c; i++){
        char a;
        cin >> a;
        v.push_back(a);
    }

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

    string s = "";
    for(int i=0; i<=c-l; i++){
        dfs(s + v[i], i, 1);
    }
}