[BOJ] 1759번 암호만들기 / 사용언어 : 파이썬(python)

※ 문제링크

1759번: 암호 만들기

해당문제는 DFS와 백트래킹을 일부 변형해서 풀 수 있는 문제였다. 문제 조건중 모음(1개이상)과 자음(2개이상) 최소개수가 주어졌기에 해당 조건을 추가시켜서 풀었더니 금방 풀 수 있었고, 정상적으로 작동하는 것을 확인했다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값들을 변수로 할당해주고, 알파벳은 리스트로 변환 후 내장함수를 활용하여 정렬해준다.

2. 알파벳의 모음, 자음여부를 판단할 변수들을 만들고 값을 할당한다.

3. 시작값과 모음갯수와 자음갯수를 확인해줄 변수들을 반영하여 dfs함수를 작성한다.

4. 조건에 만족하는 값이 나오면 출력해준다.

 

L, C = map(int, input().split())
alpha = input().split()
alpha.sort() # 입력받은 알파벳 정렬
check_alpha = ['a', 'e', 'i', 'o', 'u'] # 자음, 모음여부 확인용 리스트 생성
check = [False] * C
arr = []
cp_a, cp_b = 0, 0 # 자음, 모음 갯수 체크용 변수
def dfs(start, cp_a, cp_b):
    if len(arr) == L:  
        if cp_a >= 1 and cp_b >= 2: # 자음과 모음갯수 최솟값 이상이면 출력
            print(*arr, sep = '')
        return
    
    for i in range(start, C):
        if check[i]:
            continue

        arr.append(alpha[i])
        if alpha[i] in check_alpha:
            cp_a += 1
        else:
            cp_b += 1
        check[i] = True

        dfs(i, cp_a, cp_b)

        t = arr.pop()
        if t in check_alpha:
            cp_a -= 1
        else:
            cp_b -= 1
        check[i] = False
dfs(0, cp_a, cp_b)

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.