백준 boj 1759 - 암호 만들기 (파이썬, python)

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

1759번: 암호 만들기

 

백트래킹을 이용한 문제였다.

주어지는 6개의 문자 중에 4개를 뽑아 조합해야 하는데,

문자 4개 중 최소 2개는 자음, 1개는 모음이 되어야 한다.

 

백트래킹을 통해 모든 가능성을 체크하면서, 

모음을 포함하는지에 대한 여부와 자음을 2개 이상 포함하는지에 대한 여부를 함수로 판단하였고,

위 조건에 만족되는 경우에만 출력 할 수 있게 해주었다.

 

code

 

vowel = ['a', 'e', 'i', 'o', 'u']
l, c = map(int, input().split())
words = list(map(str, input().split()))
words.sort()
ans = []
visited = [0] * c

def is_vowel(ans): # 모음 포함 여부
    for i in range(len(vowel)):
        if vowel[i] in ans:
            return 1
    return 0

def is_two_cons(ans): # 자음 2개 포함 여부
    cnt = 0
    for i in range(len(ans)):
        if ans[i] not in vowel: # 모음이 아니면 cnt를 1 더한다 = 자음
            cnt += 1
    if cnt >= 2:
        return 1
    else:
        return 0

def dfs(iter):
    if len(ans) == l:
        if is_vowel(ans) and is_two_cons(ans): # 모음 1개 이상, 자음 2개 이상
            print(''.join(ans))
            return
    for i in range(iter, c):
        if not visited[i]:
            ans.append(words[i])
            visited[i] = 1
            dfs(i)
            visited[i] = 0
            ans.pop()
dfs(0)