[DFS] 암호 만들기 (백준 1759번)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
char arr[15];
bool visited[15];
int l, c;
int moum;
int jaum;
 
vector<char> str;
 
void dfs(int cur, int start)
{
    if (cur == l && moum >= 1 && jaum >= 2)
    {
        for (int i = 0; i < l; i++)
        {
            cout << str[i];
        }
        cout << endl;
        return;
    }
    for (int i = start; i < c; i++)
    {
        if (!visited[i])
        {
            visited[i] = true;
            str.push_back(arr[i]);
            if (arr[i] == 'a' || arr[i] == 'e' || arr[i] == 'i' || arr[i] == 'o' || arr[i] == 'u')
            {
                moum++;
                dfs(cur + 1, i);
                moum--;
                str.pop_back();
                visited[i] = false;
            }
            else
            {
                jaum++;
                dfs(cur + 1, i);
                jaum--;
                str.pop_back();
                visited[i] = false;
            }
        }
    }
}
 
int main(void)
{
    cin >> l >> c;
 
    for (int i = 0; i < c; i++)
    {
        cin >> arr[i];
    }
    sort(arr, arr + c);
 
    dfs(0, 0);
}

마음 같아서는 분류를 back tracking 이라고 기재하고 싶은데, 그러질 못하겠다.

내 코드가 너무 엉성하기 때문에.

 

모음과 자음의 개수가 문제 조건으로 있는 걸 보지 못해서 매개변수에 넣지 못했다.

그래서 나중에 전역 변수로 처리했다.

사실, 이렇게 해도 큰 문제는 없긴 하다, 백 트래킹의 정의에도 부합하기는 한다.