[알고리즘 문제] 백준1759 - 암호 만들기

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

1759번: 암호 만들기

보통 재귀에서 사전적 순서라는 문제가 나오면 for문에서 시작하는 index값을 매개변수로 넘겨주어 이전값이 등장하지 못하도록 하는 방법을 사용합니다. 단, 먼저 입력받은 알파벳이 정렬되어 있어야 합니다.

 

먼저 temp[]배열에 입력받은 알파벳을 모두 넣고 정렬해 줍니다. 그리고 재귀를 돌리는데 인자로 index와 depth를 사용합니다.

index는 사전적 순서를 만족하기 위해 for문의 시작값을 +1씩 증가해주고

depth는 temp는 기저조건과 temp에 값을 넣을 위치를 정해줍니다.

 

check()는 해당 문자열이 최소1개의 모음, 최소2개의 자음으로 이루어져 있는지 검사합니다.

 

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

using namespace std;

int visited[123] = {0};
char arr[16];
char temp[16];

int L, C;

bool check()
{
    int consonant = 0; // 자음
    int vowel = 0;     //  모음

    for (int i = 0; i < L; i++)
    {
        char c = temp[i];

        if (c == 97 || c == 101 || c == 105 || c == 111 || c == 117)
        {
            vowel++;
        }
        else
        {
            consonant++;
        }

        if (vowel >= 1 && consonant >= 2)
        {
            return true;
        }
    }
    return false;
}

void dfs(int index, int depth)
{
    if (depth == L)
    {
        if (check())
        {
            for (int i = 0; i < L; i++)
            {
                cout << temp[i];
            }
            cout << "\n";
        }

        return;
    }

    for (int i = index; i < C; i++)
    {
        temp[depth] = arr[i];
        dfs(i + 1, depth + 1);
    }
}
int main()
{
    cin >> L >> C;

    for (int i = 0; i < C; i++)
    {
        char c;
        cin >> c;
        arr[i] = c;
    }

    sort(arr, arr + C);
    dfs(0, 0);

    return 0;
}