[BOJ, Python] 1759 - 암호 만들기 ( with Backtracking )

1759번: 암호 만들기

좀 더 응용된 백트래킹 문제이다. N-Queen처럼 한가지 함수를 더 활용하여 모음 1개, 자음 2개를 만족하지 않으면 뱉어내는 방식으로 구현하려다가, 함수 속에 추가 변수를 넣어 모음과 자음의 개수를 카운트, 그리고 만족하지 않으면 추가하지 않는 방식으로 구현하였다.

L, C = map(int ,input().split())
alpha = list(map(str, input().split()))
alpha.sort()
visit = [False] * C
ans = list()

# n: 알파벳 개수, word: 만들어진 단어, a, b: 자음과 모음의 개수, idx: 마지막 알파벳의 위치
def dfs(n, word, a, b, idx):
	# 개수가 맞을 때, 자음과 모음의 개수를 충족할 때 추가
    if n == L:
        if a >= 1 and b >= 2:
            ans.append(word)
        return
        
    for i in range(n, C):
        if not visit[i]:
            visit[i] = True
            # 마지막 알파벳의 위치가 현재 알파벳의 위치보다 앞에 있어야만 추가
            if idx < i:
                if alpha[i] in ["a", "e", "i", "o", "u"]:
                    dfs(n + 1, word + alpha[i], a + 1, b, i)
                else:
                    dfs(n + 1, word + alpha[i], a, b + 1, i)
            visit[i] = False
            
dfs(0, "", 0, 0, -1)
print(*ans, sep= "\n")