[Python](DFS/백트래킹) 백준 1759번 : 암호 만들기

---

<접근 방법>

1. 모든 가능한 경우의 수를 살펴봐야 하므로 '백트래킹'임을 추론한다.
2. [조건]에 유의한다.
   - 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성
   - 알파벳이 증가하는 순서로 암호 배열
3. 먼저 알파벳을 sort로 정렬해놓고,
   백트래킹을 통해 암호의 길이가 L이면서 모음(count)이 1개 이상이면서 자음(C-count)이 2개 이상일 경우, 그 암호를 출력하도록 한다. (모음인 알파벳을 선택할 경우 count + 1을 해준다.)

def dfs(n, word, count):
    if n == C:
        if len(word) == L and count>0 and C-count>=2:
            print(word)
        return
    if candidates[n] in vowels: # 선택한 알파벳이 모음일 경우
        dfs(n+1, word+candidates[n], count+1)
    else:   # 선택한 알파벳이 자음일 경우
        dfs(n+1, word+candidates[n], count)
    dfs(n+1, word, count)   # 현재 해당 알파벳을 선택하지 않고 넘길 경우


L, C = map(int, input().split())
vowels = {'a', 'e', 'i', 'o', 'u'}  # 모음에 
candidates = list(input().split())
candidates.sort()   # 알파벳이 증가하는 순서로 암호 배열 위함
dfs(0, '', 0)

이해가 되지 않는 부분이 있으면 질문 주세요. 감사합니다.