문제

1759번: 암호 만들기

풀이

• 백트래킹으로 해결하였음
  • 근데 다른 사람들 풀이 보니까 그냥 DFS랑 조건만 잘 맞춰줘도 풀리는 것 같다.
• 🌟 백트래킹에 감이 아직 잘 안 잡힌 것 같아서, 다음에 다시 한번 풀어볼것
• 암호의 배치는 무조건 오름차순이여야 하기 때문에, alphabets 배열을 오름차순 정렬하고 이전에 사용한 문자의 바로 다음 문자부터 탐색할 수 있도록 alphabet_index 인자를 추가하였음

#include <iostream>
#include <algorithm>

using namespace std;

// * 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 
// * 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성
// * 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열
// * 문자의 종류는 C가지

int l, c; // ? l: 암호의 길이, c: 암호에 사용 가능한 알파벳 갯수
char alphabets[15]; // ? 암호에 사용 가능한 알파벳들 (사전 오름차순으로 저장)
bool visited[15]; // ? 각각의 문자가 암호에 사용되었는지 저장하는 배열 (각 문자에 대응되는 순서는 alphabets와 동일)
char result[15]; // ? 완성된 암호를 저장하는 배열

bool isVowel(char c) { // 주어진 문자가 모음인지 검사하는 함수
    if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
        return true;
    }
    return false;
}

// index: 현재 추가될 문자가 들어갈 위치
// alphabet_index: 이전 자릿수에 배치된 암호의 알파벳 인덱스 - 암호의 배치는 오름차순으로 되어야 하므로, alphabet 배열에서 이전 암호의 알파벳의 다음 알파벳부터 탐색해야 한다.
// vowel: 암호가 완성되었을 때 모음의 갯수가 조건을 만족하는지 검사해야 하므로 추가
void dfs(int index, int alphabet_index, int vowel) {
    if (index == l) { // 하나의 암호가 완성되었다면, 암호 출력 후 함수 종료 (다음 암호가 들어가야 할 인덱스 번호 == 현재까지 완성된 암호 길이)
        if (vowel > 0 && index - vowel >= 2) { // 단, 조건에 성립하는 경우에만 출력한다. - 모음 1개 자음 2개 이상
            for (int i = 0; i < l; ++i) {
                cout << result[i];
            }
            cout << '\\n';
        }
        return ;
    }

		// 앞 자릿수에 사용된 알파벳보다 사전상 뒤에 위치한 알파벳부터 탐색한다.
    for (int i = alphabet_index; i < c; ++i) {
        if (!visited[i]) {
            visited[i] = true;
            result[index] = alphabets[i];
            if (isVowel(alphabets[i])) {
                dfs(index + 1, i + 1, vowel + 1);
            } else {
                dfs(index + 1, i + 1, vowel);
            }
						// 다음 가짓수를 탐색하기 위해 방문처리 해제 + 암호에서 해당 문자 삭제
            visited[i] = false;
            result[index] = 0;
        }
    }
}

int main() {
    cin >> l >> c;

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

    sort(alphabets, alphabets + c); // 사전상 오름차순으로 정렬해두기
    // a, c, i, s, t, w

    dfs(0, 0, 0);

    return 0;
}