[BOJ / Python] 1759 - 암호 만들기

1759번: 암호 만들기

풀이

혼자 풀다가 막혀서 다른 풀이를 봤다. 완전탐색을 위해 문자열을 쌓아두는 지역변수 리스트가 각각의 DFS마다 다르게 적용된다는 것을 알아야 풀 수 있는 문제였다. 살짝 헷갈리는 문제여서 잊을 때마다 풀어야겠다.

 

완전탐색을 하기 위한 dfs 함수를 선언한다.

depth를 더하며 돌다가 depth가 주어진 수 C가 되는 순간 완전탐색 리스트에 문자열을 추가하고 return한다.

 

완전탐색의 흐름은 이렇게 될 것이다.

4 6
a t c i s w
['a']
['a', 'c']
['a', 'c', 'i']
['a', 'c', 'i', 's']
['a', 'c', 'i', 't']
['a', 'c', 'i', 'w']
['a', 'c', 's']
['a', 'c', 's', 't']
['a', 'c', 's', 'w']
['a', 'c', 't']
['a', 'c', 't', 'w']
['a', 'c', 'w']
['a', 'i']

a를 넣고 c를 넣고 i를 넣으면서 재귀함수가 실행된다.

트리 구조로 뻗어나간다고 생각하면 이해가 쉽다.

코드

l, c = map(int,input().split())
pw = list(map(str,input().split()))
pw.sort()
password = []
wantam = []
# L자리의 암호를 얻기 위한 dfs
def dfs(depth, index, l, c):
    if depth == l:
        wantam.append(''.join(password))
        return
    for i in range(index, c):
        password.append(pw[i])
        # print(password) # 여기서 찍어보면 흐름을 이해하기 쉽다.
        dfs(depth+1, i+1, l, c)
        password.pop() # pop을 해주어야 값이 쌓이지 않는다.

def solution(arr):
    for i in arr:
        vows = 0
        cons = 0
        for j in i:
            if j in 'aeiou':
                vows += 1
            else:
                cons += 1
        if vows>=1 and cons>=2:
            print(i)
    return
dfs(0,0,l,c)
solution(wantam)