</aside>

문제 정리

<aside> 👉🏿 암호의 자릿수 L이 주어진다.

암호를 구성하는데 쓰이는 알파벳의 개수 C가 주어진다.

C개의 알파벳이 주어진다.

위 입력값을 토대로 C개의 알파벳을 L의 자릿수 만큼 사전식으로 모두 출력하자.

여기서 조건은 최소 한개의 모음 (a, e, i, o, u)와 최소 두개의 자음이 필요하다.

</aside>

# 입력값
4 6
a t c i s w

# 출력값
acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

접근 방법

<aside> 👉🏿 백트래킹 dfs방식으로 탐색해 나가는 방향으로 생각해보았다.

인덱스를 늘려나가는 방식으로 백트래킹을한다.

</aside>

코드 진행

전체코드

<aside> 👉🏿 입력값을 받아준다.

주어진 알파벳은 바로 리스트화 시켜주고 정렬시켜준다.

</aside>

import sys

# 입력값 readline으로 대체
def input():
    return sys.stdin.readline()

l, c = map(int, input().split())        # l = 암호 자리수 제한 / c = 주어지는 문자의 수
word_list = sorted(input().split())     # 알파벳을 바로 리스트화 시키고 오름차순 정렬
vowel_list = ["a", "e", "i", "o", "u"]  # 모음 리스트
results = []

<aside> 👉🏿 백트래킹 함수 작성

이부분은 언제나 항상 어렵다.

알고리즘은 아래와 같다

index부터 주어진 알파벳의 개수까지 반복한다.
path에 dfs방식으로 알파벳을 붙혀나간다. 여기서 index를 하나씩 늘려나가 중복값을 없애나간다.
path의 자릿수가 만족되면 check함수를 불러 모음과 자음 개수 충족시 정답처리를 한다. </aside>

def backtrack(index, path):
    # path 길이가 암호 자릿수와 일치하면
    if len(path) == l:
        # 모음과 자음의 개수 충족시 정답 처리
        if check(path):
            results.append(''.join(path))
        return
    
    # 인덱스와 정답리스트를 누적시켜나가면서 백트래킹
    for i in range(index, len(word_list)):
        backtrack(i + 1, path + [word_list[i]])

<aside> 👉🏿 여기서 어려웠던 부분은 인덱스를 증가시킬 때, 중복값이 계속 발생된다는 점이였다.

아래는 이전에 작성했던 코드로 index 증가를 index + 1로 해주었을 때이다.

이렇게 되면 결과값이 중복값이 제거되지 않고 나온다.

</aside>

    # 인덱스와 정답리스트를 누적시켜나가면서 백트래킹
    for i in range(index, len(word_list)):
        backtrack(index + 1, path + [word_list[i]])

acis
acit
aciw
acss
acst
acsw
acts
actt
actw
acws
acwt
acww
aiss
aist
aisw
aits
aitt
aitw
aiws
aiwt
aiww
asis
asit
asiw
asss
asst
assw
asts
astt
astw
asws
aswt
asww
atis
atit
atiw
atss
atst
atsw
atts
attt
attw
atws
atwt
atww
awis
awit
awiw
awss
awst
awsw
awts
awtt
awtw
awws
awwt
awww
ccis
ccit
cciw
ciis
ciit
ciiw
ciss
cist
cisw
cits
citt
citw
ciws

<aside> 👉🏿 왜그럴까 한참 고민을 해봤는데,

index에 + 1 을 해주는게 잘못 되었다.

인자로 넘겨주는 index를 늘려줄 경우 depth별로 같은 인덱스를 늘려주기 때문에 중복값이 발생했다.

따라서 코드를 i + 1로 수정해주어야 했다.

설명하기 어려워 그림으로 그려보았다.

</aside>