[Python] 1759 암호 만들기

1. 문제 📚

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

2. 입출력 예 📋

3. 알고리즘 ✅

백트래킹 문제이므로 조건을 제대로 봐야한댜

조건1. 중복된 문자가 없을 것

조건2. 알파벳이 암호에서 증가하는 순서대로 배열 됐을 것

조건3. 최소 한개의 모음 최소 2개의 자음

4. 소스코드 💻

처음에 실패해서 뭐지 했는데 조건3을 안따졌었다 아래는 백준 질문게시판에 있던 반례이다

input:
3 6
a e i c d z

output:
acd
acz
adz
cde
cdi
cez
ciz
dez
diz​

import sys

input = sys.stdin.readline

L, C = map(int, input().strip().split())
alphabet = sorted(input().split())

visited = [False for _ in range(C)]
aeiou_arr = ['a', 'e', 'i', 'o', 'u']
password = []

def aeiou_check(password):
    aeiou_count = 0
    rest_count = 0
    for p in password:
        if p in aeiou_arr:
            aeiou_count += 1
        else:
            rest_count += 1
    return [aeiou_count, rest_count]

def dfs(start, count):
    global alphabet
    aeiou_count, rest_count = aeiou_check(password)
    # 조건3)
    if len(password) == L and  aeiou_count > 0 and rest_count >= 2:
        print(''.join(password))
        return
	
    # 조건2)
    for i in range(start, C):
    	# 조건1)
        if visited[i]:
            continue

        password.append(alphabet[i])
        visited[i] = True
        dfs(i, count + 1)
        visited[i] = False
        password.pop()

dfs(0, 0)