[BOJ] 1759 암호 만들기

솔직히 백트래킹이나 완전탐색이 뭔지 대략적으로 느껴지긴 하지만 정확히 이게 ~다 라고 못하겠습니다.. 그냥 다 돌아본다 이런 느낌은 받고 있습니다.

이번 같은 경우는 dfs로 구현을 해보았는데 일단 입력받은 문자를 정렬시키고 사용할 문자의 인덱스값을 함수에 전달시켜줘서 무조건 이전 인덱스보다 뒤에, 즉 사전순으로 정렬되도록 하였습니다. 총 전달하는 값은 4개의 값을 전달시켜주었습니다. (현재 단어, 가장 마지막에 사용한 문자의 인덱스, 자음의 개수, 모음의 개수) 이렇게 4개를 전달시켜주었고, c와 단어의 길이가 같아지면 자음의 개수와 모음의 개수가 같다면 print하고 return 아니면 그냥 return 해주었습니다.

자음 모음 판별은 그냥 a e i o u가 들어간 리스트에 해당 스펠링이 들어있나 없나를 구한 뒤 자음에는 not을 붙여서, 모음에는 그냥 전달해주었습니다.

from sys import stdin
input=stdin.readline

l,c=map(int,input().split())
spelling=sorted(input().rstrip().split())
moeum_list=['a','e','i','o','u']

def dfs(word,_idx,jaeum,moeum):
    if len(word)==l:
        if jaeum>1 and moeum>0:
            print(''.join(word))
        return
    for i in range(_idx+1,c):
        is_moeum = spelling[i] in moeum_list
        dfs(word+[spelling[i]],i,jaeum+(not is_moeum),moeum+is_moeum)

dfs([],-1,0,0)

이쁘게 잘 짜여진 것 같습니다.